10
$\begingroup$

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:

  1. 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.

The literature is full of ways to extend Bloom filters: for pattern matching, set queries, small subset queries, etc.

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:

  1. It admits sublinear-time additions and queries. (Ideally constant time)
  2. There exists some probability of error (usually false positive).
  3. 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.

$\endgroup$
  • 1
    $\begingroup$ Re: "It admits sublinear-time additions and queries. (Ideally constant time)", how do you specify an element (a set) in constant time? And when you say "linear time", what are you taking to be your measure of input size? $\endgroup$ – Neal Young Nov 4 '17 at 3:17

Your Answer

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

Browse other questions tagged or ask your own question.