Hacker News Reader

Comment by bob1029 | Hacker News Reader

I have always been fascinated by our ability to make these sorts of tradeoffs, but I also worry that making this tradeoff in the first place is an intermediate compromise taken in favor of a more fundamental rework of a problem space.

If you find yourself rolling dice to figure out if something is in a set or not, you may want to step back and look at how you track membership and identity things.

Determinism (testability) is such a wonderful thing. Sure, you can make these filters appear deterministic in controlled setting (i.e. a recorded log of system inputs), but there's no way you could tell me how the execution would flow in a real world situation with live data wherein you cannot anticipate future events.

View on HN

Probabilistic data structures are used when certainty is not needed.

Bloom filters for example can serve as a filter: to work only on 50% of the data to effectively speed up your calculations by 100%.

If 50% of your misses are bloom filtered away, you got rid of 50% of your lookups to storage.

---------

In fact, most cryptography only works off of probability. Not only keys or RNG, but also on routine algorithms like finding a prime number.

> In fact, most cryptography only works off of probability. Not only keys or RNG, but also on routine algorithms like finding a prime number.

Usually in cryptography problems when we assume that our assumptions hold (e.g. there's no better method than a semi sophisticated brute force), you get that probability down to a negligible number. And I recall learning that some key generating systems will even have a list of known cracked large primes, and check to make sure what it generates isn't in that list (in case the systems RNG is biased.)

With a tiny bit of extra cost, a very expensive check can sometimes be omitted early.

Imagine your mailbox out in your yard has a slightly faulty indicator: Sometimes when it's ON, there's actually no mail. But you know for a fact that when it's OFF, you definitely have no mail. So you can look out your window to determine whether you might have mail.

If the indicator saves you more unnecessary trips to the mailbox than it causes by failing to indicate, it's a good thing to have overall.

That's what bloom filters do. They sometimes save you needless work. The fact that "sometimes" isn't deterministic doesn't detract from its usefulness.

The probability part of data structures like bloom filters are intrinsic, and are fundamental to the actual reason they are used.

At the set sizes they are useful for, you simply have to make trade offs for performance reasons, and the trade off you are making is explicit.

If you are are using a bloom filter, you know upfront that false positives will happen. That is a fundamental part of the code you will write, it isn’t something you will discover at a later date. You will write tests for false positives. It is well understood what the probabilities are for false positives.

If you can’t live with that in your code, you might not be able to work on the sorts of workloads that bloom filters are good for.

Reply on news.ycombinator.com