HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

state of the art of subset, set containment and partial match queries

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
containmentthematchartstatepartialandqueriessubsetset

Problem

The subset query problem is defined as:

Given a list D of size N where the entries are subsets of a universe with m elements, create a datastructure that detects for every query-set Q if there exists a set P in D so that Qis a subset of P

I was wondering what are the best known algorithms to solve this problem. I couldn't find any recent publications, just this work from 2002:
Subset Queries

There it is stated, that the subset query problem is equivalent to the set containment problem as well as the partial match problem.

Any help would be appreciated.

Solution

I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.

Context

StackExchange Computer Science Q#75915, answer score: 4

Revisions (0)

No revisions yet.