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.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
968 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 ...
7
votes
0answers
335 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 ...
7
votes
0answers
699 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 ...
2
votes
0answers
37 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 ...
1
vote
0answers
25 views

Probability of string misidentified in Bloom filter

I'm attempting a question related to Bloom filters: Our Bloom filter uses $3$ different independent hash functions $H_1, H_2, H_3$ that each take any string as input and each return an index into a ...
1
vote
0answers
44 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 ...
1
vote
0answers
99 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)...
1
vote
0answers
235 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
308 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
29 views

Is it efficient to use large scale data algorithms on disk?

Is it efficient to use algorithms like locality sensitive hashing and bloom filters on disk instead of memory for very large datasets where even these structures cannot be saved in memory?
0
votes
0answers
169 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 ...