[Dailydave] approximate string matching - Bloom filters

[Martin Roesch]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Mateusz,

Sorry it didn't work out, guess I got it backwards! :)

      -Marty

On Sep 1, 2006, at 2:19 PM, Mateusz Berezecki wrote:

> On 9/1/06, Fausett, Mark (US SSA) <mark.fausett at baesystems.com> wrote:
>> Bloom filters are approximate in a different sense though -- Think of
>> them as space efficient, but lossy token sets; you put a bunch of  
>> tokens
>> in, and subsequently can query whether a particular token was placed
>> into the set; to some degree of confidence.
>> Bloom filters are subject to false positives -- they'll sometimes
>> incorrectly tell you that a token is in the set -- but not false
>> negatives.  Because hashing functions are used to insert tokens  
>> into the
>> bloom filter, the false positives have nothing to do with approximate
>> string matches.
>>
>
> By trial end error I already discovered this really unwanted  
> behavior :-/
>
> It's very good for representing what is not in the set rather than  
> representing
> the set itself.
>
> Mateusz
> _______________________________________________
> Dailydave mailing list
> Dailydave at lists.immunitysec.com
> http://lists.immunitysec.com/mailman/listinfo/dailydave
>

- --
Martin Roesch - Founder/CTO, Sourcefire Inc. - +1-410-290-1616
Sourcefire - Security for the Real World - http://www.sourcefire.com
Snort: Open Source IDP - http://www.snort.org


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iD8DBQFE+Ndnqj0FAQQ3KOARAq7+AJ4j4s9inQ1aQsYyCD1Sx9gmzUdQUQCeKJDt
3lrJrj0VJG+9twrg3ip3Buc=
=ML7k
-----END PGP SIGNATURE-----