Questions tagged [bloom-filters]
Questions involving the probabilistic data structure Bloom filter which is used to test if a given item is in a data set.
0
votes
1answer
35 views
Quick and space-efficient way to find whether two sets intersect
I hope you can help me -
Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don'...
4
votes
1answer
125 views
In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?
Multiple resources, such as Wikipedia, state that if you have an $m$-bit Bloom filter with $n$ elements inserted, then the optimal number $k$ of hash functions to use is
$k = \frac{m}{n} \ln 2$
This ...
0
votes
1answer
24 views
Bloom Filter which does not fit in RAM [closed]
Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?
0
votes
0answers
57 views
Bloom Filters and supporting deletion without having False Negatives
I've been struggling to see if a bloom filter variant would work for my problem.
I'm trying to create a bloomfilter that supports deletion. A counting bloom filter immediately pops up as a possible ...
1
vote
0answers
37 views
Double Hashing Collision
Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use
$ g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two
...
2
votes
2answers
66 views
Does Bloom filter with false positive rate greater than 0.5 make sense?
If the false positive error rate is greater than 0.5 then a Bloom filter is no different from coin flip, right?
Still, if one does implement this data structure with, say, P=0.55 then it would still ...
1
vote
0answers
73 views
Bloom filters vs storing hashes as numbers
In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
2
votes
2answers
36 views
Cuckoo filters for non powers-of-2
The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and ...
3
votes
0answers
32 views
Altering the size of a Hash
Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different ...
3
votes
1answer
264 views
hamming distance of bloom filters
In the introduction of Distance-Sensitive Bloom Filters the authors state:
The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can ...
2
votes
0answers
154 views
what are the performance differnces (space and time complexity) between count-min sketch and quotient filter?
what is the space and time complexity (lookup, insertion) of count-min sketch and quotient filter?
I could not find these complexities.
I would like to make a program which find the frequencies of ...
1
vote
0answers
229 views
Is the ratio between a bloom filter intersection and a bloom filter union equal to that of their original sets?
Given two sets, S1 and S2, and their corresponding bloom filters, BF1 and BF2, is there a way to prove that |BF1 ∩ BF2|/|BF1 ∪ BF2| = |S1 ∩ S2|/|S1 ∪ S2| (we can assume both bloom filters are ...
0
votes
0answers
101 views
Optimally sized bloom filter for two different sets
Given a set with n inserted elements and a desired false positive probability p, we can find the minimum number of bits in the bloom filter m by computing -n*ln(p)/(ln2)2
Suppose we have two sets of ...
7
votes
0answers
327 views
What was the first public reference to bloom filters where the number of hash functions vary?
In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter.
This idea is ...
3
votes
1answer
246 views
Heuristic analysis of Bloom filters
I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters.
It's all based on the following assumption:
All $h_{i}(x)$'s are uniformly ...
1
vote
1answer
73 views
What do you call a “non-probabilistic Bloom Filter”?
One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is.
It is a technique for caching ...
3
votes
2answers
300 views
Achieving better than the theoretical False Positive Rate for Bloom Filters
I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements ...
4
votes
1answer
469 views
Understanding Murmur3
The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety ...
1
vote
1answer
104 views
Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?
I show from Wikipedia that the optimal number of hash functions is:
$k =\frac{m}{n}\ln{2}$.
However it's not obvious for me why, even after reading the Wikipedia article (such as the one on false ...
11
votes
0answers
763 views
Alternative to Bloom filter for extreme parameters
A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).
I am interested in a ...
4
votes
1answer
247 views
Ways to perform “batch” Approximate Member Queries efficiently
In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number ...
6
votes
0answers
605 views
Double Hashing and Variations for Bloom Filters
I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively
...
5
votes
1answer
480 views
Why do we need “Bloom Filters” if we can use hash tables?
A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no.
If we can use hash tables where we have O(1) in best time, ...
2
votes
1answer
152 views
Bloom filter variant
I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits ...
24
votes
5answers
2k views
Is there an anti-Bloom filter?
A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in ...
1
vote
1answer
82 views
Why do we use several bits instead of a single bit for storage of objects in Bloom Filters
Bloom filters are a variant of hash tables except it is much more space efficient at the cost of a low probability of false positives .
How it works : Assume there are 10000 bits , 3 hash functions ...
5
votes
1answer
1k views
Deleting in Bloom Filters
I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete ...
4
votes
3answers
369 views
Why do Bloom filters work?
Let's say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a ...
7
votes
2answers
916 views
Bloom filter and perfect hashing
A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position.
To mitigate the effect of hash collision, multiple ...
3
votes
2answers
1k views
Bloom Filter for 208 million URLs
I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it ...
