Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which I'm hoping some "Bloom-like" solution will hold:
Suppose I have some universe set $U$, and the things I care about are subsets of $U$. In other words, they are elements of the power set $2^U$. I want to add elements to the Bloom-like filter one at a time. Each time I add, I want to check the following things:
- Is this element already in the list? 2a. Is this element a proper superset of something already in the list? 2b. OR, is this element a proper subset of something already in the list?
I only need to implement one of the superset/subset queries for my application - doesn't matter which one. If I can handle one case, I'm good.
Standard Bloom filters can only handle the first case, so I'm looking for a way to handle the last two as well.
I've been digging but the literature is fairly convoluted and I lack a good starting point here: the set query ones don't appear to be constant time, and nothing seems to be quite what I'm looking for. If anyone is familiar with the literature and knows a solution to the exact problem specified above, I would appreciate a good reference.
To be specific, I am looking for a data structure which has the following characteristics:
- It admits sublinear-time additions and queries. (Ideally constant time)
- There exists some probability of error (usually false positive).
- The error rate decreases with the size of the filter.
FWIW, the compact approximator approach looked interesting, and possibly something you could tweak to get what I'm after, but I wasn't sure how to do it.