2
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Bob Jan 20 '12 at 5:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.