Part 1: Introducing Filters and Probabilistic Searching

In my Data Structures and Algorithms in JavaScript book, we studied Dictionary implementations for exact searches. In this article series, we will explain what probabilistic searches are, when they may be needed, and cover Filters, a way to do these searches, showing several data structures with complete JavaScript code, plus examples and even questions for you to work out. This could have been an addendum to Chapter 11 in the book (new title: "Bags, Sets, Maps, and Filters"?) but I prefer a new number (Chapter 11½!) to not modify existing chapter numbers.

---

Introducing Filters

A common problem in Computer Science is determining whether a key is in a set or map. However, sometimes you just want to know whether the key is absent (for example, to avoid accessing a database, external service, or web page) and can accept false positives if the search just says, "the key may be in the set." This kind of probabilistic search is a cheap pre-filter in front of a more expensive, authoritative access or check.

For example, you could be building a password checker. You have a database with billions of compromised usernames. Given a specific user, you want to quickly check whether he may be in the set. If you had added all compromised users to a Bloom Filter, you could do a very quick check; if the filter says "Absent", you are 100% sure the account wasn't compromised. On the other hand, if the filter says "May be present", then, and only then, you'd search thefindfind extensive database or call an external service to (far more slowly) do the definitive test. Using the filter can speed up many searches, requiring a slow check only for a few.

Figure 11½ -1: Algorithm for exact searches with filters

A full dictionary for exact answers requires more space, and probabilistic searches reduce that significantly, at the cost of occasionally saying "maybe" when the true answer is "no". When we have a large key set and tight memory or latency requirements, and we can tolerate a low, controllable rate of unnecessary extra work, we can accept these false positives. And remember, negative answers will always be correct and final.

ADT for Filters

A filter's behavior is characterized by a parameter with no analog in Dictionary ADTs: the false-positive rate, usually written ε. This number actually quantifies how often you may get false-positive answers. It's expressed as a probability: ε=0.01 means roughly a 1% chance that a find operation will incorrectly return true. This isn't a bug or an implementation quirk; it's a value you consider when deciding which structure to use and how to size it.

Also, as with other structures such as hash tables (see the Hashing section in chapter 11) you must specify how many values (n) you expect to store. Given n and ε, we can calculate the right size for specific filter implementations. The following table shows the Filter ADT.

Table 11½-1: Operations on Filters

There are several interesting comments here.

• In the add operation, we do not worry if a value is repeatedly added to the filter. However, in some implementations this may cause issues later, as we'll see.

• The remove operation may not be required or allowed. Some structures cannot support it at all; some can. An important issue here is that removing a value that wasn't in the filter may cause false negatives, which breaks the ADT contract!

• More extreme still, some filters trade away both add and remove operations after initial construction in exchange for better space and speed; in these cases, the create operation takes the whole set of values used to build the filter instead of the n parameter.

• Finally, we could support an empty? operation (given a filter, determine whether it is empty) and a size operation (given a filter, determine how many values it includes) but I'll leave those implementations up to you.

Comparing Dictionaries and Filters

To summarize, Filters differ from Dictionaries in three important ways:

1. Compactness - Filter implementations use substantially less space than Dictionary implementations, typically a small constant number of bits per element. 
2. One-sided error - The find operation never produces a false negative. However, it may produce false positives at a rate bounded by ε.
3. Tunable accuracy - ε is a construction parameter and can be driven down (at the cost of more space) as far as the application needs. Dictionaries are always 100% accurate; filters, by definition, are not.

We've covered all the considerations to keep in mind when planning filters; now let's move on to actual implementations.

---

Bye for now! In the next article in the series, we will start with Bloom Filters, the first implementation we'll be considering.