5
$\begingroup$

I'v been tackling a problem with bloom filters. I have a basic version working on paper, but I need to be able to put a large interval of numbers into the filter at a given time.

Let I be an interval within [0,U]. The problem is to put I into set S, as well as query if I is within set S using an optimized bloom filter.

For inserting one element l into S, I hash it using k unique hash functions and set B[h(l)] = 1 for each hash function.

To query if element l is within S, I must check for all hash functions 1 to k if B[h(l)] = 1. If so, I can claim l is within S with some probability.

For an interval of elements, I assume there is a faster way to store each element in interval I into set S, but I'm not sure how to get started other than iterating and hashing each element one by one for each hash function. I also have to check membership. Any help would be appreciated!

$\endgroup$
  • $\begingroup$ What is the difference between this question and your other one? $\endgroup$ – Aperson123 Nov 16 '17 at 20:17
  • $\begingroup$ This one had 4 views. When I posted my second one, this one shot up to 15 views. I assume my wording of this question was poorly done since no one answered so I tried to redo it. Sorry, new to stack exchange. $\endgroup$ – bloom Nov 16 '17 at 20:29

Your Answer

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

Browse other questions tagged or ask your own question.