Vernon Schryver <v...@rhyolite.com> wrote: > > How many hash functions are you using, what are they, and how do you > know that they are sufficiently independent to give a tolerable false > positive rate without using as much RAM as a single classic hash table?
You can use a linear combination of two hash functions to get an arbitrary number of Bloom filter indexes - it's as good as the same number of independent functions. http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf At the moment I'm just using BIND's sockaddr_hash routine, adapted to hash on the network prefix and to provide two variant hashes. It has the nice property of being randomised when the server starts. > What is your estimate for the memory required for a simple hash > based scheme? I haven't done the sums yet, sorry. > Do you believe that single set of Bloom filter parameters can serve an > interesting class of installations without using more RAM than a classic > hash function? To understate it--I don't. Of course not :-) But I think it will be possible to set them automatically based on overall query rate. I only started work on this on Friday so it's early days :-) Tony. -- f.anthony.n.finch <d...@dotat.at> http://dotat.at/ Shannon: Variable 3 at first in southeast, otherwise northerly 4 or 5, occasionally 6 later. Moderate. Showers. Good. _______________________________________________ dns-operations mailing list dns-operations@lists.dns-oarc.net https://lists.dns-oarc.net/mailman/listinfo/dns-operations dns-jobs mailing list https://lists.dns-oarc.net/mailman/listinfo/dns-jobs
