Bloom Filters : Reduced number of bits

79 Views Asked by At

How can a bloom filter that uses m bits be reduced into a bloom filter with (m-1) bits, without using the whole dictionary? I've been stuck on this question for a long time and any help would be appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

There is a B.F trick known as halving a B.F When halving, the new B.F will only require m/2 bits which is enough for 2^(b-1)