Efficient way of finding subsets and supersets in a collection of sets

Question

Is there any efficient algorithm or data structure for looking up supersets and subsets on a collection of sets?

Example:

# collection of sets
>>> col = [{1,2,3},{2,3,4},{4,5,6,7}]

>>> subsets_of({1,2,3,4}, col)
[{1,2,3},{2,3,4}]

>>> supersets_of({4}, col)
[{2,3,4},{4,5,6,7}]

Answer 1

In the general case, no, other than brute force search methods.

However, there are various techniques for doing linear time searches depending on the type of data you have. For example, if the element values were always less than 32 (or 64) then you could create an integer with the bits set for the values present and OR them to find out if the set was a subset. If the values are less than a 100 million or so you can create a giant boolean array where each array element is 1 if the set contains the value, or 0 if it does not. Then the subset lookup is linear time. A similar method is possible for solving the superset problem in linear time.