[Haskell-cafe] Re: [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters

Achim Schneider barsoap at web.de
Sat May 31 14:29:04 EDT 2008

Aaron Denney <wnoise at ofb.net> wrote:

> On 2008-05-30, Achim Schneider <barsoap at web.de> wrote:
> > Bryan O'Sullivan <bos at serpentine.com> wrote:
> >
> >> A Bloom filter is a probabilistic data
> >> structure that provides a fast set membership querying capability.
> >> It does not give false negatives, but has a tunable false positive
> >> rate.  (A false positive arises when the filter claims that an
> >> element is present, but in fact it is not.)
> >> 
> > /me squints.
> >
> > Please tell me that this isn't reversible.
> Tell me what you mean by "reversible".  You can't, for instance,
> extract the items in the set.
I guess invertible would have been the right word, though it's still

Turning it into something that does not give false positives, but has a
tunable false negative rate.

Without looking at the algorithm, I imagine it working somewhat like a
hashtable, and this inversion would utterly destroy my intuition.

(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited. 

More information about the Haskell-Cafe mailing list