Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same as the address for a house in USA. Albert doesn't have that much money to travel to America to confirm whether the key is a hoax or not, by going to the address of the key. He certainly doesn't have the money for a house in America. If the key turns out to be a hoax, Albert would have a very hard time to make a living in America. It would cost him dearly. One day, a postman who knew all the addresses in America visited Europe. He happened to meet Albert.

Can the postman carry a certain information that is less than the information of all addresses in America to confirm whether Albert's key is valid or not? Then what is the information and what kind of operations is made to make the confirmation?

Assume all information is numeric here.

Background: I was looking at implementing a hash table for already known keys and I was wondering whether there exists efficient lookups where I don't have to visit a bucket in a hash table(America) to confirm whether a key exist or not.

  • $\begingroup$ Welcome to Computer Science! Your question sounds interesting. I know it is supposed to be obvious. However, I could not find the critical definition that defines how or when Albert's key can be considered valid. Is that also part of the question? Please clarify in the question. $\endgroup$ – Apass.Jack Oct 31 '18 at 21:18
  • $\begingroup$ Hi, what I meant with valid was if the key leads to a house in America or if it is just a fake key that doesn't lead to a house in America. $\endgroup$ – einstein Oct 31 '18 at 22:08

Using Bloom filters you can store membership of $n$ elements using approximately $-1.44\cdot\log_2(p)\cdot n$ bits, where $p$ is your probability of a false positive (it does not have false negatives).

This is assuming you have perfect independent hash functions (which is a reasonable enough assumption).

So if Albert wants an 0.1% chance of wasting his time the postman needs to carry $\approx 14.4$ bits of information per address, which is definitely less than the amount of bits to uniquely store an address.

  • $\begingroup$ Originally, I was hoping for a non probabilistic solution, but I guess it is maybe too much to ask. $\endgroup$ – einstein Oct 31 '18 at 22:16
  • $\begingroup$ @einstein, the bloom filter itself returns a Yes/No answer. The filter may lie and say Yes, but it will never say No and be wrong. There are two reasons for the wrong Yes: a match is detected because the hash functions somehow returned numbers that look like a match even if it isn't; or the data was actually there but was deleted (to rebuild the filter you have to start from scratch so it is potentially very expensive in comparison to the few false positive). $\endgroup$ – Alexis Wilke Oct 4 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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