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 <b...@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. > _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
