9 votes
Accepted

In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?

This balances two considerations: The more hash functions you have, the more bits will be set in the Bloom filter when you create the filter (because each element you insert causes up to $k$ bits to ...
D.W.'s user avatar
  • 158k
5 votes
Accepted

Does Bloom filter with false positive rate greater than 0.5 make sense?

A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a ...
Pseudonym's user avatar
  • 22k
4 votes
Accepted

What is the point of Bloom's filter if its false positive rate is so high?

$m$ is the total size of the filter in bits, not the number of bits per entry. With $m=1000$ the formula gives a false positive rate of around 10%, roughly the same as the 1000-bit list of hashes (...
benrg's user avatar
  • 2,112
4 votes
Accepted

Understanding Murmur3

You have asked two questions. I will answer them one by one. Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is ...
Yuval Filmus's user avatar
3 votes
Accepted

Ways to perform "batch" Approximate Member Queries efficiently

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.) This might be slow, however, ...
jbapple's user avatar
  • 3,340
3 votes

Deleting in Bloom Filters

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when ...
Kent Munthe Caspersen's user avatar
3 votes

Distinct elements count of huge multiset

Let me simplify your third step: count the number of elements in your multiset which are not in the map, and add to it the number of elements in the map. Suppose that your elements are $x_1,\ldots,...
Yuval Filmus's user avatar
2 votes
Accepted

Heuristic analysis of Bloom filters

A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$. ...
Yuval Filmus's user avatar
2 votes
Accepted

What do you call a "non-probabilistic Bloom Filter"?

This is related to the notion of "fast path, slow path" from computer systems. In systems, one common optimization method is: if there is a common case that can be handled fast and is common, first ...
D.W.'s user avatar
  • 158k
2 votes

Achieving better than the theoretical False Positive Rate for Bloom Filters

Your question includes the equation $$ (1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k} $$ But that is not actually an equation; it is only an approximation.
jbapple's user avatar
  • 3,340
2 votes

Join with Bloom-filters

A Bloom Filter will typically be used to eliminate mismatches quickly, since it produces true negatives, but some false positives. A join (specifically, an equi-join) which is expected to have some ...
KWillets's user avatar
  • 1,274
2 votes

Quick and space-efficient way to find whether two sets intersect

Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, ...
j_random_hacker's user avatar
2 votes

Integer set disjointness query on sketches with something like homomorphic hashing

Here is one simple idea -- not sure if it's practical. Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In ...
j_random_hacker's user avatar
2 votes
Accepted

How is the optimal number of hashes is derived in bloom filter?

We want to find the value of $k$ that minimizes the function $$ f(k) = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ When $m$ is large, $1 - 1/m \approx e^{-m}$, and so $$ f(k) \approx \...
Yuval Filmus's user avatar
2 votes
Accepted

Find dominated or subsumed linear inequalities efficiently

Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier. In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon>0$ unless the Strong ...
D.W.'s user avatar
  • 158k
2 votes
Accepted

Efficiently count distinct in large range

I think the Google Scholar keywords you're looking for are "sliding window" and "hyperloglog". I found "Cardinalities estimation under sliding time window by sharing ...
jbapple's user avatar
  • 3,340
2 votes

What is the point of Bloom's filter if its false positive rate is so high?

No, your proposed scheme with cryptographic hash functions does not do a better job than Bloom filters. Your scheme outputs $10n$ bits, which is way more than $m$ bits. You are comparing a Bloom ...
D.W.'s user avatar
  • 158k
2 votes
Accepted

Set intersection using bloom intersection

Without any special knowledge about the distribution of data, you cannot do better than that. In the worst case, you have to read every element of $B$. There can be $\Theta(n)$ elements of $B$. So, ...
D.W.'s user avatar
  • 158k
1 vote

What is the point of Bloom's filter if its false positive rate is so high?

Sure, you can store an approximate representation with only log storage, but the error rate will be insanely high, so it will likely be useless in practice. For instance, one approximate ...
D.W.'s user avatar
  • 158k
1 vote

Splitting the output of a wide hash in lieu of multiple independent hashes

This is a heuristic. Any use of hash functions is a heuristic. Here is a justification why it is a reasonable/plausible thing to do. Suppose our hash function is a uniform random function $h:\{0,1\}^...
D.W.'s user avatar
  • 158k
1 vote
Accepted

Optimal parameters for a Bloom filter

When using SHA256, the maximum possible filter size is $m=2^{256}$. A 256-bit value can index into $2^{256}$ possible indices into the array. This is more than adequate. For instance, a 3-bit hash ...
D.W.'s user avatar
  • 158k
1 vote
Accepted

Is the equality of Bloom filters analogous to set equivalence?

It is possible to find an upper bound on the probability of a collision in the fingerprint. Suppose the Bloom filter uses $k$ hash functions and maps into a bit array of size $m$. The case $k=1$ is ...
D.W.'s user avatar
  • 158k
1 vote

Are joins/pullbacks of bloom filters possible?

Ok, so the short answer to this question seems to be a "yes, but it grows quickly in size". You can view the bloom filters for each tuple element as vectors of bits. In that case, their ...
saolof's user avatar
  • 131
1 vote
Accepted

Integer set disjointness query on sketches with something like homomorphic hashing

If you use bijective hash functions, you can recover the original keys from filter structures like cuckoo filters or quotient filters. The reason is that these are essentially quotienting dictionaries,...
jbapple's user avatar
  • 3,340
1 vote

Integer set disjointness query on sketches with something like homomorphic hashing

Yes. Use any linear function as your hash function. If $h(x)= \alpha x + \beta \bmod n$, where $\alpha,\beta$ are fixed constants, then $$h(x+\delta) = h(x) + \alpha \delta \bmod n.$$ Consequently, $...
D.W.'s user avatar
  • 158k
1 vote

How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?

The easiest and secure method of doing this is making a token an (id, signature) pair where you randomly generate a fixed-size id (e.g. 128-bits) using a method that avoids collisions (a hash of a ...
orlp's user avatar
  • 13.1k
1 vote
Accepted

Quick and space-efficient way to find whether two sets intersect

Use a partitioned Bloom filter for testing set intersection. It has lower FPR than unpartitioned (standard) Bloom filters. To intersect two partitioned Bloom filters: AND the bit vectors for all the ...
Paul Chernoch's user avatar
1 vote

Bloom Filter which does not fit in RAM

A Bloom filter doesn't have "buckets". You can make a Bloom filter of any size you want. The smaller it is, the higher the false positive rate. This should be covered in any good introduction to ...
D.W.'s user avatar
  • 158k
1 vote

Does Bloom filter with false positive rate greater than 0.5 make sense?

In the same way that 0.5 is the error of a coin flip, 0.166666 is the error of a die throw. There's nothing sacred in the probability 0.5. A Bloom filter gives you a guarantee that a coin flip ...
Yuval Filmus's user avatar
1 vote
Accepted

Cuckoo filters for non powers-of-2

Yes, it is possible. Use $$h_2(x) = \text{hash}(\text{signature}) - h_1(x) \bmod n.$$ The theory behind this: if $c$ is a constant, the function $$f(t) = c - t \bmod n$$ is an involution for any $...
D.W.'s user avatar
  • 158k

Only top scored, non community-wiki answers of a minimum length are eligible