Return to Question

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.

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.

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?

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.