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

[Achim Schneider]

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

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.