12

Going with Patrick87's hash idea, here's a practical construction that almost meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can be easily made negligibly small. Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$. Let $H$ be a secure cryptographic ...


10

The second paragraph of the Wikipedia article on Bloom filters says the following, with a citation to Bloom's original 1970 paper. Bloom proposed the technique for applications where the amount of source data would require an impracticably large hash area in memory if "conventional" error-free hashing techniques were applied. He gave the example of a ...


8

No, it is not possible to have an efficient data structure with these properties, if you want to have a guarantee that the data structure will say "new" if it is really new (it'll never, ever say "not new" if it is in fact new; no false negatives allowed). Any such data structure will need to keep all of the data to ever respond "not new". See pents90's ...


7

I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions. As this is a very simple solution, it might be considered as a folklore. Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems): http://www.dca.fee.unicamp....


7

I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical dynamic perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative. Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected ...


6

Using the formula from wikipedia for Bloom filter false positives, your proposal would have a false positive probability of about 0.00726%. This assumes, among other things, that good hash functions are used. The formula is: $(1 - (1 - [1/m])^{kn})^k$ where $m$ is the number of bits in the filter, $k$ is the number of hash functions and $n$ is the number ...


6

Given that you want to insert $n$ words into the Bloom filter, and you want a false positive probability of $p$, the wikipedia page on Bloom filters gives the following formulas for choosing $m$, the number of bits in your table and $k$, the number of hash functions that you are going to use. They give $ m = - \frac{n \ln p}{(\ln 2)^2} $ and $$ k = \frac{m}{...


6

What about just a hash table? When you see a new item, check the hash table. If the item's spot is empty, return "new" and add the item. Otherwise, check to see if the item's spot is occupied by the item. If so, return "not new". If the spot is occupied by some other item, return "new" and overwrite the spot with the new item. You'll definitely always ...


5

A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a potential performance issue, but not a correctness issue. One obvious example is where the filter is used to avoid a more expensive check. Let's try to quantify ...


5

This balances two considerations: The more hash functions you have, the more bits will be set in the Bloom filter when you create the filter (because each element you insert causes up to $k$ bits to be set in the filter). The more bits that are set, the higher the risk of false positives. The more hash functions you have, the less likely that one of them ...


4

In the case where the universe of items is finite, then yes: just use a bloom filter that records which elements are out of the set, rather than in the set. (I.e., use a bloom filter that represents the complement of the set of interest.) A place where this is useful is to allow a limited form of deletion. You keep two bloom filters. They start out empty....


4

You have asked two questions. I will answer them one by one. Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is reasonable, then all small sets of seeds should look "the same". I don't know the Murmur3 family, but it's probably reasonable enough. Note that linear ...


3

Let me simplify your third step: count the number of elements in your multiset which are not in the map, and add to it the number of elements in the map. Suppose that your elements are $x_1,\ldots,x_n$. For a given hash $h$, let $x_{i_1},\ldots,x_{i_\ell}$ be the elements hashing to $h$ (in order). If $\ell = 1$, then the elements won't be added to the map ...


3

This is how I use Bloom filter: suppose that full dictionary check is 10x slower than checking a bit in the Bloom filter. Then if you make a Bloom filter having $N$ bits per dictionary word, then average time required for one check would be $1+10/N$. For example, with $N=8$ (i.e., use one byte in Bloom filter per dictionary word), the avg.time will be 2.25 ...


3

Let's analyze how many hash bits you need in your new scheme versus a Bloom filter. First of all, we need to agree about terminology. I will use $q$ to represent the probability of a false positive. For a Bloom filter the design problem of choosing $m$ and $k$ given that you want to hold $n$ elements with false positive rate $q$ is solved by $k = -\lg_2 q$...


3

This is explained in Wikipedia. Given $n,m$, the false positive probability is $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ This is the quantity we want to minimize. While the exact expression is hard to minimize exactly, we can use the approximation $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx (1-e^{-kn/m})^k, $$ which is ...


3

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.) This might be slow, however, since the lookups are random and have bad cache behavior. There are a few ways to fix this. I'd suggest: Use a blocked bloom filter (from Cache-, Hash- and ...


2

You choose the size of your Bloom filter according to the expected occupancy. If your Bloom filter is full of 1s then it's too small for the number of words you're putting it. Words in a document tend to repeat, so when estimating how big the filter should be, count the number of unique words in your document.


2

I think the Bloom filter gives you something the perfect hash function does not - it can test membership. The PHFs I know return some answer for any key you apply them to. If the key you supplied is not in your hash set, some value is still supplied. This is fine if you are storing all of the keys that are in your set somewhere and the PHF just gives a ...


2

A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$. We can improve on this bound by calculating instead the probability that a bit is 0, that is, that it is not hit. For a bit not to be hit, it has to be missed ...


2

This is related to the notion of "fast path, slow path" from computer systems. In systems, one common optimization method is: if there is a common case that can be handled fast and is common, first test whether the input falls into that case and if so solve it and return immediately; otherwise, fall back to the complex computation. For instance, the slow ...


2

Your question includes the equation $$ (1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k} $$ But that is not actually an equation; it is only an approximation.


2

Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, and also maintain a mapping from each element to the set of all sets that contains it (e.g. using a hashtable of hashtables). When you add an element $x$ to a ...


1

A Bloom Filter will typically be used to eliminate mismatches quickly, since it produces true negatives, but some false positives. A join (specifically, an equi-join) which is expected to have some non-matching keys can be sped up by pre-processing the valid keys from one table into a Bloom filter. The join operator tests each key from the other table ...


1

A Bloom filter doesn't have "buckets". You can make a Bloom filter of any size you want. The smaller it is, the higher the false positive rate. This should be covered in any good introduction to Bloom filters, of which there are many.


1

In the same way that 0.5 is the error of a coin flip, 0.166666 is the error of a die throw. There's nothing sacred in the probability 0.5. A Bloom filter gives you a guarantee that a coin flip cannot – it has no false negatives. Even if its false positive rate is 0.9, it still gives you some information. Whether or not a high false positive rate is ...


1

Yes, it is possible. Use $$h_2(x) = \text{hash}(\text{signature}) - h_1(x) \bmod n.$$ The theory behind this: if $c$ is a constant, the function $$f(t) = c - t \bmod n$$ is an involution for any $c$ and any $n$, since $$f(f(t) = c - (c-t) = t \pmod n.$$ Therefore, we can use the hash of the signature as the constant $c$. This gives you a scheme that ...


1

Let $S,T$ be two sets of size $n$. Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x_S$ be the $m$-bit vector corresponding to $S$, and $x_T$ the $m$-bit vector corresponding to $T$. If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then the expected value of the Hamming distance between these two bit-...


1

I just want to add in here, that if you are in the fortunate situation, that you know all of the values $v_i$ that you might possibly see; then you can use a counting bloom filter. An example might be ip-addresses, and you want to know every time one appears that you have never seen before. But it is still a finite set, so you know what you can expect. The ...


1

Consider Bloom filters in which $k$ hash functions are used. If we look up a value which is in the filter, then we always conclude that it is indeed in the filter. Things are more complicated when we look up a value which is not in the table; we could erroneously conclude that it were in the table. Suppose the filter is of size $n$, and $m$ values were put ...


Only top voted, non community-wiki answers of a minimum length are eligible