<p>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:</p>

<p>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:</p>

<ol>
<li>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?</li>
</ol>

<p>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.</p>

<p>Standard Bloom filters can only handle the first case, so I'm looking for a way to handle the last two as well.</p>

<p>The literature is full of ways to extend Bloom filters: for <a href="https://www.cs.cmu.edu/~dga/papers/ffbf-alenex2011.pdf" rel="noreferrer">pattern matching</a>, <a href="http://www.vldb.org/pvldb/vol9/p408-yang.pdf" rel="noreferrer">set queries</a>, <a href="https://web.stanford.edu/~ashishg/papers/inverted.pdf" rel="noreferrer">small subset queries</a>, etc.</p>

<p>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.</p>

<p>To be specific, I am looking for a data structure which has the following characteristics:</p>

<ol>
<li>It admits sublinear-time additions and queries. (Ideally constant time)</li>
<li>There exists some probability of error (usually false positive).</li>
<li>The error rate decreases with the size of the filter.</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2017-11-04T03:17:57.153Z
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?
Neal Young
CC BY-SA 4.0
2020-03-15T22:11:26.677Z
@NealYoung by bitmask of fixed size?
Tomilov Anatoliy
CC BY-SA 4.0
2020-03-16T12:30:58.233Z
So you have in mind that your sets come from a universe of constant size?
Neal Young
CC BY-SA 4.0
2020-03-24T05:59:46.603Z
No. Are you familiar with Bloom Filters? The size of the Bloom Filter is independent of the number of elements of the set.
Mike Battaglia
<reference-request><ds.data-structures>
Bloom filter variant for constant-time subset/superset queries
Mike Battaglia
# Bloom filter variant for constant-time subset/superset queries

(Asked by: username_0 on 2017-10-24)

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](https://www.cs.cmu.edu/~dga/papers/ffbf-alenex2011.pdf), [set queries](http://www.vldb.org/pvldb/vol9/p408-yang.pdf), [small subset queries](https://web.stanford.edu/~ashishg/papers/inverted.pdf), 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.

**Tags:** reference-request, ds.data-structures
> **Comments:**
> **username_1**: 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?  
> **username_2**: @NealYoung by bitmask of fixed size?  
> **username_1**: So you have in mind that your sets come from a universe of constant size?  
> **username_0**: No. Are you familiar with Bloom Filters? The size of the Bloom Filter is independent of the number of elements of the set.  

---

## 0 answers

