Questions tagged [bloom-filter]

Bloom filter is a probabilistic data structure that tells you if a value might be in the set.

bloom-filter
Filter by
Sorted by
Tagged with
147 votes
8 answers
66k views

What is the advantage to using Bloom filters?

I am reading up on Bloom filters and they just seem silly. Anything you can accomplish with a bloom filter, you could accomplish in less space, more efficiently, using a single hash function rather ...
headache's user avatar
  • 8,637
26 votes
3 answers
18k views

Which hash functions to use in a Bloom filter

I've got the following question about choosing hash functions for Bloom filters: Which functions to use? In nearly every document/paper you can read that the hash functions used in a Bloom filter ...
Torsten's user avatar
  • 291
27 votes
5 answers
24k views

How many hash functions does my bloom filter need?

Wikipedia says: An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m ...
dicroce's user avatar
  • 46.1k
15 votes
3 answers
13k views

python bit array (performant)

I'm designing a bloom filter and I'm wondering what the most performant bit array implementation is in Python. The nice thing about Python is that it can handle arbitrary length integers out of the ...
lollercoaster's user avatar
9 votes
1 answer
6k views

What is an XOR filter?

There's a relatively new data structure (2020) called the XOR filter that's being used as a replacement for a Bloom filter. What is an XOR filter? What advantages does it offer over the Bloom filter? ...
templatetypedef's user avatar
74 votes
9 answers
16k views

Opposite of Bloom filter?

I'm trying to optimize a piece of software which is basically running millions of tests. These tests are generated in such a way that there can be some repetitions. Of course, I don't want to spend ...
user avatar
59 votes
6 answers
21k views

Modern, high performance bloom filter in Python? [closed]

I'm looking for a production quality bloom filter implementation in Python to handle fairly large numbers of items (say 100M to 1B items with 0.01% false positive rate). Pybloom is one option but it ...
Parand's user avatar
  • 105k
31 votes
4 answers
13k views

Need memory efficient way to store tons of strings (was: HAT-Trie implementation in java)

I am working with a large set (5-20 million) of String keys (average length 10 chars) which I need to store in an in memory data structure that supports the following operation in constant time or ...
hashable's user avatar
  • 3,831
20 votes
5 answers
10k views

Bloom filter or cuckoo hashing?

Which do you prefer and why? They both can be used to accomplish similar tasks but I'm curious as to see what people have used in actual applications and their reasoning for doing so.
J B's user avatar
  • 231
8 votes
1 answer
2k views

Is there any probabilistic data structure that gives false negatives but not false positives?

I need a space efficient probabilistic data structure to store values that I have already computed. For me computation is cheap but space is not - so if this data structure returns a false negative, I ...
pathikrit's user avatar
  • 33.2k
2 votes
2 answers
3k views

Using hash functions with Bloom filters

A bloom filter uses a hash function (or many) to generate a value between 0 and m given an input string X. My question is how to you use a hash function to generate a value in this way, for example an ...
dangerstat's user avatar
19 votes
3 answers
8k views

Bloom filter usage

I am struggling to understand the usefulness of the bloom filter. I get its underlying logic, space compaction, fast lookups, false positives etc. I just cannot put that concept into a real-life ...
Bober02's user avatar
  • 15.1k
10 votes
1 answer
902 views

How to map hashfunction output to bloomfilter indices?

Can anyone help me by providing an outline on how the hash function output is mapped to bloom filter indices? Here is an overview on bloomfilters.
N. F.'s user avatar
  • 901
7 votes
6 answers
18k views

Bloom Filter Implementation

Using Bloom filter, we will be getting space optimization. The cassandra framework also has an implementation of Bloom Filter. But in detail, how is this space optimization achieved?
UVM's user avatar
  • 9,814
7 votes
2 answers
6k views

Bloomfilter and Cassandra = Why used and why hashed several times?

I Read this: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html My Questions: 1.) Is it correct, that Cassandra only uses the bloom filter, to find out the SST (Sorted String ...
jens's user avatar
  • 17k
6 votes
2 answers
2k views

Near Duplicate Detection in Data Streams

I am currently working on a streaming API that generates a lot of textual content. As expected, the API gives out a lot of duplicates and we also have a business requirement to filter near duplicate ...
thickblood's user avatar
4 votes
1 answer
1k views

C++ Storing a dynamic_bitset into a file

Sort of a follow up to How does one store a vector<bool> or a bitset into a file, but bit-wise? Basically I am writing a bitset as a binary file with the follow code: boost::dynamic_bitset<...
cjustin's user avatar
  • 115
3 votes
2 answers
1k views

Why Does a Bloom Filter Need Multiple Hash Functions?

I don't really understand why a bloom filter requires multiple hash functions (say, SHA and MD5). Why not just make a bigger SHA hash, for example, and then break it up into multiple parts and treat ...
user541686's user avatar
  • 207k
2 votes
3 answers
825 views

non-repeating random numbers

I need to generate around 9-100 million non-repeating random numbers, ranging from zero to the amount of numbers generated, and I need them to be generated very quickly. Several answers to similar ...
user2635469's user avatar
2 votes
2 answers
4k views

An algorithm to find the difference of two set A and B with size n

There are two set A and B, and the size of both sets is n. How to find every elements of A that is not in B (A-B), with O(n). What data structure should I use (bloom filter?)
jarins's user avatar
  • 21
2 votes
1 answer
1k views

Can Bloom Filters in BigTable be used to filter based only on row ID?

BigTable uses Bloom filters to allow point reads to avoid accessing SSTables that do not contain any data within a given key-column pair. Can these Bloom filters also be used to avoid accessing ...
nday's user avatar
  • 229
1 vote
1 answer
6k views

Bloom Filter: evaluating false positive rate

Given a fixed number of bits (eg. slot) (m) and a fixed number of hash function (k), how one compute the theoretical false positive rate (p) ? According to Wikipedia http://en.wikipedia.org/wiki/...
Yann Droneaud's user avatar
0 votes
1 answer
333 views

What is a d-Left Counting Bloom Filter?

Could someone explain me, in a simple way, the d-left counting Bloom filter and in particular the use of fingerprints and remainders? And is there a good Python implementation of it?
user15982670's user avatar
0 votes
1 answer
150 views

What's the fastest way to figure out if a pointer is part of a set in C?

Given a pointer on a struct, I need to very quickly find whether it is part of a set (that I have to define/implement myself). I may consider a technique like Bloom Filter, but don't really know how ...
Patrick Allaert's user avatar