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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
36 views

Number of non-zero elements in intersection of two bloom filters

Let us assume I use bloom filters of size $m$ bits with $k$ hash functions. Now I have two set $X$ and $Y$. Let $B(X)$ be bloom filter of the set $X$. In general I know that $B(X\cup Y)= B(X) \lor B(Y)...
Galois group's user avatar
0 votes
0 answers
23 views

Data structure for detecting duplicate entries efficiently

In search of an efficient data structure to store some sort of list hash that I can compare to a value to obtain a probability of it already being in the list. Perhaps it makes more sense defined as ...
maxy's user avatar
  • 1
1 vote
1 answer
249 views

Set intersection using bloom intersection

Let $A \subseteq Z$, where $Z=\{1,2,3,\cdots,n\}$. Now given any $B \subseteq Z$, we need to check whether $A \cap B =\varphi$ or not. I am looking for a randomized algorithm. I am trying to implement ...
Rma's user avatar
  • 123
0 votes
4 answers
689 views

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

This and this agree that there will be near 100% false positive rate with Bloom's filter should number of elements in the set ($n$) be greater than the number of bits in the filter ($m$). E.g. if $n=...
caveman's user avatar
  • 115
0 votes
1 answer
43 views

Efficiently count distinct in large range

I have a pubsub channel where an event is fired every time a user logs in, and I want to be able to query the unique users in a date range. Solutions I thought: Put the data in bigquery, and then use ...
Mascarpone's user avatar
1 vote
0 answers
48 views

Bloom filter creating different arrays from two input sets

Assume a bloom filter that is composed of $H = \{H_1, ..., H_k\}$ hash functions, and uniformly maps elements from an input set $X$ to an array $A$ of size $n$. Let $X_1, X_2$ (not same) be two input ...
Aris Konstantinidis's user avatar
0 votes
0 answers
44 views

An efficient, probabilistic data structure for storing relationships between elements

I am fascinated by the bloom filter data structure. Is there a similar probabilistic data structure that can efficiently store and update the relationships between certain elements and the strength of ...
magnetlion's user avatar
2 votes
1 answer
81 views

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

Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of ...
Dumbfounded's user avatar
1 vote
1 answer
268 views

Optimal parameters for a Bloom filter

My first question here. Please do not judge me much if this is a too simple. Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ ...
yarchik's user avatar
  • 125
0 votes
1 answer
56 views

Is the equality of Bloom filters analogous to set equivalence?

I have two multisets $A$, $B$ where $A \subseteq B$. Using these two sets, we construct two Bloom filters $BF(A), BF(B)$; both using bitsets of size $n$ with the same $k$ hash functions. What's the ...
zetaprime's user avatar
  • 123
1 vote
2 answers
40 views

Are joins/pullbacks of bloom filters possible?

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
saolof's user avatar
  • 131
0 votes
0 answers
98 views

Bloom filter variant(using only half of it)

A Bloom filter is an array $B[1..m]$ of bits, together with a collection of $k$ independent ideal random hash functions $h_1,h_2,...,h_k$. To insert an item $x$ into a Bloom filter, we set $B[h_i(x)] ←...
kings's user avatar
  • 141
2 votes
1 answer
38 views

Find dominated or subsumed linear inequalities efficiently

Problem statement Given a set of $N$ linear inequalities of the form $a_1x_1 + a_2x_2 + ... + a_Mx_M \geq RHS$, where $a_i$ and $RHS$ are integers. The inequality $A$ dominates or subsumes inequality $...
Simon's user avatar
  • 232
4 votes
3 answers
106 views

Integer set disjointness query on sketches with something like homomorphic hashing

Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
taktoa's user avatar
  • 364
2 votes
1 answer
838 views

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

As mentioned in several resources such as Wikipedia the optimal number of hash functions for a bloom filter is known to be $$k=\frac{m}{n} \ln 2$$ but how is this number derived? It seems that it's ...
mahdi's user avatar
  • 123
2 votes
0 answers
235 views

How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
M A's user avatar
  • 141
3 votes
1 answer
122 views

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

Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental ...
Taytay's user avatar
  • 131
0 votes
0 answers
39 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?
user321423's user avatar
1 vote
0 answers
97 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 ...
yee's user avatar
  • 11
1 vote
1 answer
2k views

Join with Bloom-filters

can you tell me how i can use a bloom-filter by a joining operation with two tables? let's assume that: Table A ={A_id,B_id,age}, Table B = {B_id, color}. now i want to use a bloom-filter so i can ...
Apfelsaft's user avatar
3 votes
1 answer
798 views

Distinct elements count of huge multiset

I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer ...
Cedric Martin's user avatar
1 vote
3 answers
268 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'...
selotape's user avatar
  • 113
7 votes
1 answer
2k 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 ...
Mike Battaglia's user avatar
0 votes
1 answer
40 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?
Alk's user avatar
  • 101
1 vote
0 answers
63 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 ...
Nat's user avatar
  • 113
2 votes
2 answers
145 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 ...
ov7a's user avatar
  • 143
1 vote
0 answers
129 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)...
Teodor Dyakov's user avatar
2 votes
2 answers
131 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 ...
Giuseppe Ottaviano's user avatar
2 votes
0 answers
43 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 ...
quesyKing's user avatar
3 votes
1 answer
567 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 ...
Cryptonaut's user avatar
2 votes
1 answer
316 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 ...
Adi Ml's user avatar
  • 83
1 vote
0 answers
383 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 ...
Chris H.'s user avatar
0 votes
0 answers
198 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 ...
Chris H.'s user avatar
7 votes
0 answers
346 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 ...
dan's user avatar
  • 529
2 votes
1 answer
376 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 ...
FrostyStraw's user avatar
1 vote
1 answer
146 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 ...
leoger's user avatar
  • 113
3 votes
2 answers
523 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 ...
sparkonhdfs's user avatar
3 votes
1 answer
2k 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 ...
Daniel Lovasko's user avatar
2 votes
1 answer
432 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 ...
gsamaras's user avatar
  • 251
11 votes
0 answers
1k 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 ...
doc's user avatar
  • 391
4 votes
1 answer
313 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 ...
Enno Shioji's user avatar
7 votes
0 answers
997 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 ...
user3467349's user avatar
5 votes
1 answer
712 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, ...
user3378649's user avatar
2 votes
1 answer
280 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 ...
Sneftel's user avatar
  • 221
34 votes
5 answers
4k 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 ...
András Salamon's user avatar
1 vote
1 answer
128 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 ...
Computernerd's user avatar
14 votes
4 answers
7k 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 ...
Zix's user avatar
  • 259
4 votes
4 answers
515 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 ...
user220201's user avatar
7 votes
2 answers
1k 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 ...
nicolas's user avatar
  • 325
3 votes
2 answers
2k 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 ...
Aadith Ramia's user avatar