Finding a subset of a set in a collection of sets 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&#39;$ in the collection such that $S&#39; \subset S$, false otherwise.


My main criterion would be practical time efficiency.
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.