7
$\begingroup$

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 functions are used, yielding probabilistic bound if using universal hash.

We can use 10 bits per elements to have 'reasonable' error rate.

If we could directly build a perfect hash function for the set $S + \infty$, where the last element is one not present in $S$, then we could use only 1 bit per element and have perfect recovery.

What are the fundamental reasons why this reasoning is wrong ?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ How large is $S$ and why is 10 bits "reasonable"? $\endgroup$
    – Pål GD
    Jun 4, 2013 at 11:17
  • $\begingroup$ Why would S size come into play ? I might be missing something. $\endgroup$
    – nicolas
    Jun 4, 2013 at 12:29
  • 2
    $\begingroup$ Why do you think something is wrong with your reasoning? $\endgroup$
    – JeffE
    Jun 6, 2013 at 0:27
  • $\begingroup$ @JeffE It would be strange to find a huge space saving when bloom filter recognised quality is its parsimony. that said, they rely on universal hash functions so this might not be surprising. I guess to the extreme case the length of the program needed to describe the hash would itself has some kolmogorov (?) bound that limit the effectiveness. similarly, if we found a function that hashed "better" this would probably come provably at some program space cost that offset the gains. but I don't know any of this, hence my question... $\endgroup$
    – nicolas
    Jun 6, 2013 at 14:56
  • 3
    $\begingroup$ Your reasoning is perfectly sound. You can get perfect recover using only one bit per element with a perfect hash function. The resulting data structure would be completely useless, because a perfect hash function would take too long to evaluate, but it would save a lot of space! $\endgroup$
    – JeffE
    Jun 7, 2013 at 3:03

2 Answers 2

Reset to default
7
$\begingroup$

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 amortized (you might need to rebuild the data structure completely from time to time). Also Bloom filter are easier to implement. This might be arguments for using a Bloom filter, especially if you can live with false positives.

Improve this answer
$\endgroup$
2
$\begingroup$

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 pointer, or if you're only using the PHF to look up satellite data of size $O(1)$ on keys you happen to know to be in your structure. However, membership testing is harder.

In particular, storing $n$ distinct elements without error requires $n \log_2 n$ bits of storage.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.