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

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.

• May 28, 2017 at 0:07

• 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.