In order to decrease the number of false positives, I came up with a couple of possible solutions.

  1. Create two different types of Bloom filters; eg. filter1 using 3 different hash algorithms, filter2 using 3 other hash algorithms.

  2. Create two different lengths of one type Bloom filter; eg. the number of bits would be different, thus the hash modulation would be different.

  3. Create two different types of Bloom filters with two different lengths. I believe number 2 would be fastest, but would it in theory be better to use #1 (or #3), in order to (easily/quickly) reduce the number of false positives as much as possible ?

Most of the time, I would use this for short text-strings (up to approximately 20 characters) and URLs.

  • 2
    The false positive rate of a single bloom filter can already be changed through the hash functions and bits. What advantage do you hope to get from making a second bloom filter rather than pouring those resources (additional hash functions, more bits) into the existing bloom filter? – user7043 Nov 9 '14 at 18:36
  • I'm thinking that two Bloom filters of length 32 would bring better probability than a single filter of length 64. – user124114 Nov 9 '14 at 18:39
  • @PacMan-- well, you're wrong. The false positive rate will be the same. – raptortech97 Nov 9 '14 at 22:39
  • @raptortech97: Woops, I did mean to say two filters with length 32 and different hash algorithms used would be better than 1 with a length of 64 bits OR two filters using the same hash algorithms with two different lengths, such as one with length 31 and another with length 33 would be better than a single with length 64. – user124114 Nov 9 '14 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy