4
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Not sure if I got it right, but this data structure isn't very efficient for flat tries. If I have a set-trie of $\{(1, 2), (1, 3), (1, 4), \ldots, (1, 9999)\}$ and want to query for the existence of supersets of $(1, 10000)$, I have to iterate over all 9998 children of node $1$ just to realize that they all have no further descendents. $\endgroup$
    – SOFe
    Commented Apr 15 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.