[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

bloom filters (was: concurrency suggestions for Gnus)

From: Ted Zlatanov
Subject: bloom filters (was: concurrency suggestions for Gnus)
Date: Tue, 08 Feb 2011 08:41:38 -0600
User-agent: Gnus/5.110011 (No Gnus v0.11) Emacs/24.0.50 (gnu/linux)

On Tue, 08 Feb 2011 13:31:39 +0900 Miles Bader <address@hidden> wrote: 

MB> Ted Zlatanov <address@hidden> writes:
Tom> If we went the "lock anything" route, I would suggest a weak hash table
Tom> for locks, instead of putting the lock into the object.
>> A bloom filter would guarantee no false negatives, which as you noted is
>> the vast majority of the cases, requires very little space per element

MB> A bloom filter...?!

(changing the subject accordingly)

Basically a fast membership query that uses pairwise independent hash
functions.  Runs in constant time, has no false negatives, and has a
false positive rate correlated to the number of bits per element.  It
would actually be a nice addition to the Emacs core to have a C


reply via email to

[Prev in Thread] Current Thread [Next in Thread]