8
$\begingroup$

What data structures would you recommend that represent a collections of subsets of $\{1, \dots, n\}$ and support the following operations?

  • $insert(S)$: inserts $S$ in the collection.
  • $query(S)$: returns true if there exists $S'$ in the collection such that $S' \subset S$, false otherwise.

My main criterion would be practical time efficiency.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Recommendation requires criteria. What are your criteria? For example, simplicity, space, or time? The more specific you are, the more likely you get answers that are useful to you. $\endgroup$
    – Tsuyoshi Ito
    Jul 21, 2011 at 14:58
  • $\begingroup$ You're right, thank you for pointing it out. My main criterion would be practical time efficiency. $\endgroup$
    – Caleb Poucher
    Jul 21, 2011 at 16:07
  • 1
    $\begingroup$ Do you know how many insertions you'll do relative to the number of queries you'll do? It's possible to build an enormous data structure (size exponential in $n$) that will let you query a set $S$ in $O(n)$ time. On the other hand, if $m$ is the total number of inserted subsets, you can do a naive search with no additional storage in $O(nm)$ time. Everything in between, I think, will be a trade off. $\endgroup$
    – James King
    Jul 21, 2011 at 22:39
  • $\begingroup$ The number of queries is a lot bigger than that of insertions (perhaps by a factor of $100$). I considered representing the sets as points in $\{0,1\}^n$ and using range trees, but it would also lead to a size which is exponential in $n$. I wonder if there is a way to avoid the exponential factor in $n$ for insertions and the linear factor in $m$ for queries. $\endgroup$
    – Caleb Poucher
    Jul 21, 2011 at 23:27
  • $\begingroup$ Do you have a ballpark idea of what $n$ and $m$ might be? $\endgroup$
    – James King
    Jul 22, 2011 at 0:16

2 Answers 2

Reset to default
1
$\begingroup$

Your problem sounds to me a lot like Information Retrieval(IR). There you have a collection of sets of words (also known as documents) and you want to find not only existence, but all the sets/documents that satisfy the query condition.

Since the set elements are numbers , you can take advantage of teh apparent structure, thus a signature index would be of much use.

I would recommend taking a look at IR papers, especially related to dictionary structures, like trees, but note that space is usually an issue for those systems, whereas it might not be an issue for your case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good point, this is indeed very similar to searching for terms in documents, and the most common way of solving that is using a so-called inverted file, which works like the index of a book. You look up each term in your query in the inverted file and get a list/set of documents containing that term. You then intersect these lists to get the result. (You could, for example, use a hash table mapping item IDs to sorted lists of set IDs; the sorting helps with the intersection.) $\endgroup$
    – Magnus Lie Hetland
    Jul 27, 2011 at 10:56
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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