# Fast set indexing data structure for superset retrieval

I am given a set of sets:

``````{{a,b}, {a,b,c}, {a,c}, {a,c,f}}
``````

I would like to have a data structure to index those sets such that the following "lookup" is executed fast: find all supersets of a given set.

For example, given the set {a,c} the structure would return

``````{{a,b,c}, {a,c,f}, {a,c}}
``````

but not {a,b}.

Any suggestions? Could this be done with a smart trie-like data structure storing sets after a proper sorting?

This data structures is going to be queried a lot. Thus, I'm searching for a structure that might be expensive in build but rather fast to query.

UPDATE: I have finally used a prefix Trie as described in the paper "A New Method to Index and Query Sets", by Jorg Hoffmann and Jana Koehler.

It seems you're searching for a standard Information Retrieval algorithm. Instead of giving you the answer (which depends on factors such as frequency and cardinality of terms and the number of documents, the type of queries asked), I forward you to the excellent introductory treatise on the topic called: Introduction to Information Retrieval: http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html

Probably the chapter 'Index Construction' contains an algorithm suitable for your needs.

• Fantastic book - I studied IR with it a couple of years ago. However, I wanted to avoid making posting lists and intersecting them (even with skip pointers) as I have a rather small "language" and very long posting lists. Classic IR algorithms are better for large languages. Thank you for your suggestion. Nov 14, 2012 at 10:35

If the different kinds of elements are limited, you could build a table of flags. Each set is an array of bools where each position represents a word. The words are kept in a list, where their index is equal to the index of the bool that represents them. To find the supersets, you compare the values of the flags; to be a superset, every position with value True in the subset should contain True in the candidate set. All this can be done in O(n), which is not bad in my opinion.

Python:

``````WORDS = (
'a',
'b',
'c',
'f',
)

def values_to_words(s):
return set(WORDS[i] for i, v in enumerate(s) if v)

def words_to_values(s):
return tuple(True if w in s else False for i, w in enumerate(WORDS)) # Unoptimized

SETS = tuple(words_to_values(s) for s in (
('a','b',),
('a','b','c',),
('a','c',),
('a','c','f',),
))

def get_supersets(q):
values = words_to_values(q)
is_superset = lambda s: all(v1 or not v2 for v1, v2 in zip(s, values))
return (values_to_words(s) for s in SETS if is_superset(s))

print list(get_supersets(('a','c',)))
# [set(['a', 'c', 'b']), set(['a', 'c']), set(['a', 'c', 'f'])]
``````

Be of course careful not to build your own SQL engine. You could in fact use one for this pattern.

Also, you'll find https://stackoverflow.com/questions/1263524/superset-search useful - I just found it.

• the number of sets that will be given is expected to be very, very large (hundreds of thousands). Thus, intersecting could possibly be very expensive. Nov 12, 2012 at 12:51
• What kind of elements will the sets contain? And how many different will there be? Nov 12, 2012 at 13:13
• The elements will be words. And I expect to have around 1500 distinct words. Nov 12, 2012 at 13:14
• @Asterios I changed my answer accordingly. Nov 12, 2012 at 17:02
• I find O(n) expensive for my application. I have finally used a Trie structure from "A New Method to Index and Query Sets" by Jorg Hoffmann and Jana Koehler. Thank you for your help. Nov 14, 2012 at 10:30