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

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 ...


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 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

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....


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 ...


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

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 ...


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 ...


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 ...


2

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when inserting. When removing an element, you can then decrement all of its related integers.


2

We want to find the value of $k$ that minimizes the function $$ f(k) = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ When $m$ is large, $1 - 1/m \approx e^{-m}$, and so $$ f(k) \approx \left(1 - e^{-kn/m}\right)^k. $$ The logarithm of this is $$ \log f(k) \approx k \log(1-e^{-kn/m}). $$ The derivative of this approximation is $$ \log(1 - e^{-kn/m})...


2

Here is one simple idea -- not sure if it's practical. Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}_n(\cdot)$ is defined as before. Then $\mathsf{...


2

Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier. In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon>0$ unless the Strong Exponential Time Hypothesis is false. In particular, the special case where all coefficients are 0 or 1 and the RHS is the same for all inequalities is equivalent ...


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 ...


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