The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
14 views

bloom filter in high load/concurrency environment?

"I was asked this question in an interview, How to design a bloom filter to reduce cache access in a high load and concurrency environment. I know how bloom filter works but try to understand how high ...
5
votes
1answer
104 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
49 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 ...
18
votes
5answers
981 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
45 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
113 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
273 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 ...
6
votes
1answer
261 views

Bloom filter and perfect hashing

Bloom filter use a hash function to test membership for S by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple functions are used, ...
3
votes
2answers
480 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 ...