Filters and Probabilistic Searching - Part 1: Introduction

In my book on data structures and algorithms in JavaScript, we explored exact search implementations using dictionaries. In this series of articles, we will delve into probabilistic searches, when they are necessary, and present filters, a method for conducting these searches. This article will serve as an introduction to filters, explaining their purpose, benefits, and implementation details.

One common issue in computer science is determining whether a key is present within a set or map. However, there are scenarios where we only need to ascertain if the key is absent (for instance, to prevent accessing a database, external service, or website) and can tolerate false positives by accepting that the search might indicate the key may be in the set. Probabilistic searches function as an inexpensive pre-filter before a more precise, authoritative access or check.

To illustrate, consider a password checker. You possess a database containing billions of compromised usernames. Given a specific user, you aim to swiftly ascertain if their account may be compromised. By constructing a Bloom Filter with all compromised users, you can execute a rapid check; if the filter responds with "Absent," you can be certain the account is safe.

Conversely, if the filter indicates "May be present," you must then search the extensive database or consult an external service to definitively verify the user's status, which is significantly slower.

Figure 11½ -1 shows the algorithm for exact searches using filters. A complete dictionary for exact responses necessitates more storage, while probabilistic searches considerably reduce memory usage at the expense of occasionally reporting a "may be present" when the actual answer is "no." When dealing with a large key set, limited memory or latency requirements, and the ability to tolerate a low, controllable rate of unnecessary additional work, we can accept these false positives. Positive responses will always be accurate and definitive.

The abstract data type (ADT) for filters is defined by a parameter with no counterpart in dictionary ADTs: the false-positive rate, typically denoted as ε. This figure quantifies the likelihood of encountering false-positive answers. Expressed as a probability, ε=0.01 signifies a roughly 1% chance that a find operation will erroneously return true.

This is not an error or implementation flaw; rather, it is a value to consider when choosing a structure and determining its size. Like other data structures such as hash tables (covered in chapter 11), you must specify the number of values (n) you intend to store. Given n and ε, we can determine the optimal size for specific filter implementations.

The table below outlines the Filter ADT. Table 11½-1: Operations on Filters There are several noteworthy observations in this table. In the add operation, we do not concern ourselves with repeatedly adding the same value to the filter. However, this may cause complications in certain implementations, as we will discuss later. The remove operation may not be mandatory or permitted.

Some structures cannot support it whatsoever; others can. A critical concern here is that removing a value not present in the filter could lead to false negatives, violating the ADT contract.

Some filters go even further by forsaking both add and remove operations after initial construction in favor of improved space and speed. In these cases, the create operation accepts the entire set of values used to build the filter instead of just the n parameter. Additionally, we could support the empty? operation (determining whether a filter is empty) and the size operation (determining the number of values within a filter), but I leave the implementation of these methods as an exercise for the reader.

In comparison to dictionaries, filters differ in three significant aspects: compactness, one-sided error, and tunable accuracy. Filters utilize significantly less space than dictionary implementations, typically employing only a small constant number of bits per element. The find operation never produces a false negative but may produce false positives at a rate bounded by ε.

The value of ε acts as a construction parameter and can be minimized (at the cost of increased space) to meet the application's requirements. Dictionaries are always 100% accurate; filters, by definition, are not.

In the subsequent article of this series, we will explore Bloom Filters, the first implementation we will examine.