2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – D.W.
    Feb 9, 2020 at 18:29
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Feb 9, 2020 at 18:31
  • $\begingroup$ This looks a somewhat concise and clear problem statement: Please show what your research so far turned up and how that falls short. $\endgroup$
    – greybeard
    Feb 9, 2020 at 21:49

1 Answer 1

-1
$\begingroup$

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.

If you map all your subset into binary numbers, then you are searching in the number space.

$\endgroup$
3
  • $\begingroup$ How do you suggest searching in the number space? Using "usual" interval search, you will be looking for one interval for the first element and for many for the element mapped to the least significant bit. $\endgroup$
    – greybeard
    Feb 9, 2020 at 21:43
  • $\begingroup$ now you have every numbers, you can use binary search to find the "exact number" you want $\endgroup$ Feb 9, 2020 at 22:14
  • $\begingroup$ The catch being that I'm not looking for an exact number: look at the answer to the (a, b, c, d)-query in the question's example. $\endgroup$
    – greybeard
    Feb 9, 2020 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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