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.
Asked
Active
Viewed 78 times
0
-
1seems to be a dump of homework? – kodlu May 09 '21 at 07:00
-
Yeah, an assignment, couldn't get how to solve this – Srivatsav Palli May 09 '21 at 07:09
-
1What did you try? – Kaira May 09 '21 at 07:11
-
Actually, we need to construct the new bloom filter from this old bloom filter, without the use of all the words, but basically we have only half the bits. Like 2^b in the old, and 2^b-1 in the new, so that's the only thing I was able to figure out. Can I get an insight on this? – Srivatsav Palli May 09 '21 at 07:35
1 Answers
0
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)
Joe N
- 16
-
Thanks a lot Joe for the answer. I've searched about the halving a Bloom Filter operation after watching your answer and it was really helpful. And one last request, where can I get some real good theory about this Halving technique, like every where I go, I find only one line about it. Once again, I would like to appreciate you for being kind enough to help me out here. – Srivatsav Palli May 12 '21 at 12:27