Assuming lots of sets S = (s_1, s_2, ..., s_m) are known in advance, a series of inquiries comes. We need to quickly decide whether the given set s' is a subset of any set s_i in S or s_i is any subset of s'.
Here, the value m will be very very large, and the inquiries is frequent. How to store the sets S with which data structure or encoding way so that the inquiry is efficient. Can anyone give some suggestion for this problem?
You can see the work of Agrawal and Srikant (1994), where they mine association rules (the famous algorithm Apriori). They use a hash tree structure to check subsets' inclusions.
They used their structure (hash tree) to return any s_i is that is subset of s', but you can easily update the algorithm to also check the reverse inclusion.
That's the thesis of Srikant, see the section "subset function" page 26
- Badges
- Science topic
- Similar topics
- Mathematics