<p>There is a data structure called an "invertible Bloom filter" due to Goodrich and myself that can be used for storage: you can add and remove keys and, whenever the current number of keys is below the capacity of the structure, determine what they are with high probability (regardless of whether it was ever above capacity in the past). Goodrich and Mitzenmacher have generalized this to allow values to be associated with the keys as well.</p>

<p>However, one drawback to these structures is that they use quite a bit more space than a normal Bloom filter: basically, a logarithmic number of bits per key rather than a constant number of bits per key.</p>

<p>See </p>

<p>Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23(2): 297-306, 2011.</p>

<p>and</p>

<p>Invertible Bloom Lookup Tables
Michael T. Goodrich, Michael Mitzenmacher
arXiv:1101.2245</p>

CC BY-SA 3.0
2012-01-20T05:03:57.907Z
I've been in UC Irvine as a postdoc and I think I saw you on campus once. Thank you for the advice, I will take a look at it :)
zzzbbx
CC BY-SA 3.0
2012-01-20T02:54:44.220Z
2012-01-20T02:54:44.220Z
David Eppstein
<p>I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage.  </p>

<p>The problem with the Bloom filter is that, even if we accept that there will be false positives, the set of elements that we need to scan to see which ones are present may be very large (assuming that such set is finite). I would like to know if there is a smart way to reduce the complexity of such problems, namely, the complexity associated to the task of finding which elements are currently stored in the Bloom filter (of course with error due to false positives, if any). </p>

<p>Is there any techniques in the literature that I can look at to reduce the complexity of such task?</p>

<counting-complexity><set-theory><search-problem>
Bloom filter for storage
zzzbbx
# Bloom filter for storage

(Asked by: username_0 on 2012-01-20)

I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage.

The problem with the Bloom filter is that, even if we accept that there will be false positives, the set of elements that we need to scan to see which ones are present may be very large (assuming that such set is finite). I would like to know if there is a smart way to reduce the complexity of such problems, namely, the complexity associated to the task of finding which elements are currently stored in the Bloom filter (of course with error due to false positives, if any).

Is there any techniques in the literature that I can look at to reduce the complexity of such task?

**Tags:** counting-complexity, set-theory, search-problem


---

## 1 answers

### Answer by username_1 on 2012-01-20. Score: 6 | Accepted answer

There is a data structure called an "invertible Bloom filter" due to Goodrich and myself that can be used for storage: you can add and remove keys and, whenever the current number of keys is below the capacity of the structure, determine what they are with high probability (regardless of whether it was ever above capacity in the past). Goodrich and Mitzenmacher have generalized this to allow values to be associated with the keys as well.

However, one drawback to these structures is that they use quite a bit more space than a normal Bloom filter: basically, a logarithmic number of bits per key rather than a constant number of bits per key.

See

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23(2): 297-306, 2011.

and

Invertible Bloom Lookup Tables
Michael T. Goodrich, Michael Mitzenmacher
arXiv:1101.2245

> **Comments:**
> **username_0**: I've been in UC Irvine as a postdoc and I think I saw you on campus once. Thank you for the advice, I will take a look at it :)  

---

