3 ms·
CouchDB Bloom Filters
- kiwidrew 17y agorelated: cassandra's use of bloom filters http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-kn... and also related: murmurhash, a hash which is well-suited for bloom filters and that is much faster than SHA-1 http://murmurhash.googlepages.com/ http://murmurhash.googlepages.com/
- neilc 17y agoIt's funny that the Cassandra blog post talks about bloom filters as the "hot new thing". They were an old idea when System R* used them to do distributed joins in 1986. http://www.seas.upenn.edu/~zives/cis650/papers/r-star.pdf http://www.seas.upenn.edu/~zives/cis650/papers/r-star.pdf
- vicaya 17y agoBigtable (according to the paper), HBase and Hypertable all use bloom filters to improve performance of random reads. Here is some bloom filter test code in Hypertable to compare Jenkins' lookup3, Hsieh's SuperFastHash and Appleby's MurmurHash2: http://github.com/vicaya/hypertable/blob/4fce96592cab3fd6d0e022a0471001b0810f9f4c/src/cc/Common/tests/bloom_filter_test.cc http://github.com/vicaya/hypertable/blob/4fce96592cab3fd6d0e... MurmurHash2 is the winner in all cases I've tested.