5
$\begingroup$

I have been trying to design a variant of a bloom filter that can insert an interval of values at once, as well as query if a certain interval is in the bloom filter. I haven't been able to think of a faster case than the naive method of inserting one at a time.

Does anyone have any idea how to approach this kind of problem?

Edit: Clarification on what I mean by a bloom filter - A bloom filter is a way to store elements from a universe without using an array of the size of the universe. For example, if the universe is [1,200]. Every time I visit an element i from the universe, I have to mark somehow that I visited it. I could have an array of size 200 (each element initialized at 0) and mark that array at element i as 1 for visited. To reduce the size of this problem, we hash the element i using k hashing functions and set them all to 1 in my visited array (which is much smaller than the universe size). This leaves room for a false positive since checking if an element exists via the visited array involves checking if all locations that i hashes to are set to 1. See here for a more in depth description.

$\endgroup$
  • 1
    $\begingroup$ I edited my problem to explain what a bloom filter is in my context. $\endgroup$ – bloom Nov 16 '17 at 18:58

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.