# How to speed up finding a subset of a given set?

Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data?

For example, let's say that I have a collection of sets: (a, b) (b, c) (a, b, c, d) (a, b, c) (b, c, d) (b, e) (d, e, f) (d, f, g) (d, e, f, g)

I want to find subsets of (a, b, c, d), so the output should be: (a, b) (b, c) (a, b, c, d) (a, b, c) (b, c, d)

Is there a method to index/hash data in a way that will limit the number of collection elements that I have to scan in order to find all matches?

• Welcome to CS.SE! There are a bunch of nearly identical questions previously posted. They don't seem to offer any terribly satisfying solutions. If you are asking about a special case that differs from those other questions, I suggest you edit to summarize what you've found and make your question unique and we can take another look. Note that superset queries are in princple isomorphic to subset queries (take the complement of the sets).
– D.W.
Feb 9, 2020 at 18:29
• cs.stackexchange.com/q/75915/755, cs.stackexchange.com/q/74833/755, cs.stackexchange.com/q/109399/755, cs.stackexchange.com/q/7701/755. Dear community - should this be marked as a duplicate?
– D.W.
Feb 9, 2020 at 18:31
• This looks a somewhat concise and clear problem statement: Please show what your research so far turned up and how that falls short. Feb 9, 2020 at 21:49

if you map every element in set in S into a bit in a binary number. For set with n elements, we have n bit binary number. the $$i$$-th number takes 1 if the subset has that element. Then we can use a binary number from $$00,...,00$$ to $$11,...,11$$ to represent all the subset.