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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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