[ovs-dev] [bondlib 06/19] tag: New function tag_set_union().

Ethan Jackson ethan at nicira.com
Mon Mar 28 14:17:38 PDT 2011


I guess the only thing that makes them different from bloom filters is
how the hashing is done.  We are basically using a random hash
function, only allowing the hash to be computed once, and forcing the
caller to store the result.  Traditionally when people talk about
bloom filters, generally they have a hash function which given a flow,
for example, would always produce the same two bits for that flow.
Fundamentally it's the same data structure, just a slightly different
way of thinking about the problem.

Ethan

On Mon, Mar 28, 2011 at 2:09 PM, Ben Pfaff <blp at nicira.com> wrote:
> On Mon, Mar 28, 2011 at 01:59:34PM -0700, Ethan Jackson wrote:
>> As a side note, I finally took a moment to read how we actually
>> implemented tags.  Very cool, reminds me of a very specialized version
>> of bloom filters.
>
> I think that they really are Bloom filters.  They match the
> description for "Bloom filter" in Wikipedia.  I probably should have
> just described them as Bloom filters in the header file, but I
> originally learned about them from Knuth v3, and he doesn't (IIRC)
> call them Bloom filters even though he cites Bloom as the inventor.
>



More information about the dev mailing list