You could use a search tree. Not a “standard” one, as is used for ordered universes (real numbers, strings…) but a more general type, such as the ones hinted at by the GiST project. There are search trees for spatial queries, as well as ones based on the metric axioms, for indexing metric (distance) spaces. The general idea (of which the “less than/greater than,” interval-oriented approach of ordinary, ordered search trees is a specialization) is to decompose the data set into subsets, usually hierarchically. This hierarchy of subsets is (obviously) represented by a tree, where the children of each node represent subsets, and each node has some form of predicate, which allows you to check whether there is an overlap between the the (conceptual) set of objects relevant to your query, and those found in that subtree (i.e., subset).
For example, for a spatial tree in the Euclidean plane, each object could be a point, and the predicates could be bounding rectangles, containing all points found in or below that node. If a query is a rectangle (and you wish to find all points in that rectangle), you can recursively eliminate subtrees whose bounding rectangles don’t overlap with your query.
In your case, you could build a tree where each node contains some set structure which would allow you to detect whether your query is a subset. If not, that entire subtree can be eliminated, as your query could never be a subset of any of the child nodes (and certainly not the leaves, which would probably represent the true data).
As opposed to ordinary search trees, there is no search-time guarantee in general here—you’ll probably visit several branches, so even if you have a perfectly balanced tree, you’ll probably have a superlogarithmic running time. This is more of a heuristic approach, but it could be effective even so.
What you need, in order to build this tree, would be some form of hierarchical clustering method that would fit your data. The GiST project actually has a tree very much like what you need, with a C implementation (although it checks whether the query overlaps, not if it’s a subset; should be easy to modify). The disk-based, B-tree-style balanced tree of GiST might be overkill, though. You probably just want to cluster similar sets together, hierarchically, and you could do that using any off-the-shelf clustering algorithm, using something like Hamming distance (or something more fancy). The more similar sibling nodes are, the “tighter” the bounding predicate of the parent (that is, the set representing their union) will be—and therefore, the more efficient your search will be.
To sum up, my suggestion is:
- Represent your sets so you can check for overlap with query (bit vectors, hash tables).
- Cluster your sets hierarchically, using a suitable distance (e.g., Hamming) and an off-the-shelf algorithm.
- In each internal node, store the union of the child node sets.
- During search, traverse recursively, pruning/ignoring subtrees whose roots have sets that doesn’t overlap with your query.
If you need the tree to be dynamic, there are lots of ways of doing that as well. For example, you could recursively traverse the tree, finding the location that fits best (by going through nodes with the highest overlap/smallest Hamming distance), updating the unions (bounding predicates) as you go. Deletions are a bit more tricky, perhaps; you could just mark objects as missing, and then rebuild subtrees (or the entire structure) when the number of marked objects hits a certain threshold.
Whether this works well for your application could be hard to say a priori, but should be easy to check experimentally. Also, there is a lot of room for tweaking.