# Tag Info

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 ...
• 158k
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 ...
• 22k
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 (...
• 2,112
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 ...
• 277k
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, ...
• 3,340