Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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. –  Asterios Nov 14 '12 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 http://stackoverflow.com/questions/1263524/superset-search useful - I just found it.

share|improve this answer
    
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. –  Asterios Nov 12 '12 at 12:51
    
What kind of elements will the sets contain? And how many different will there be? –  Thijs van Dien Nov 12 '12 at 13:13
    
The elements will be words. And I expect to have around 1500 distinct words. –  Asterios Nov 12 '12 at 13:14
    
@Asterios I changed my answer accordingly. –  Thijs van Dien Nov 12 '12 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. –  Asterios Nov 14 '12 at 10:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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