[SOLVED] What is an XOR filter?

An XOR filter is designed as a drop-in replacement for a Bloom filter in the case where all the items to store in the filter are known in advance. Like the Bloom filter, it represents an approximation of a set where false negatives are not allowed, but false positives are.

Like a Bloom filter, an XOR filter stores a large array of bits. Unlike a Bloom filter, though, where we think of each bit as being its own array slot, in an XOR filter the bits are grouped together into L-bit sequences, for some parameter L we'll pick later. For example, an XOR filter might look like this:

 +-------+-------+-------+-------+-------+-------+-------+-------+-------+
 | 11011 | 10010 | 11101 | 11100 | 01001 | 10101 | 01011 | 11001 | 11011 |
 +-------+-------+-------+-------+-------+-------+-------+-------+-------+

Next, we pick three hash functions h₁, h₂, and h₃ that, like a Bloom filter, hash items to slots in the array. Those hash functions let us take an item x and compute its table code, which we do by XORing together the items in spots h₁(x), h₂(x), and h₃(x). An example of this is shown here:

 +-------+-------+-------+-------+-------+-------+-------+-------+-------+
 | 11011 | 10010 | 11101 | 11100 | 01001 | 10101 | 01011 | 11001 | 11011 |
 +-------+-------+-------+-------+-------+-------+-------+-------+-------+
             ^                       ^       ^
             |                       |       |
            h3(x)                   h1(x)   h2(x)
              
            Table code for x:   10010 xor 01001 xor 10101
                              = 01110

To complete the picture, we need one more hash function called the fingerprinting function, denoted f(x). The fingerprinting function takes a value as input and outputs an L-bit number called the fingerprint of x. To see whether x is stored in the table, we check whether the table code for x matches the fingerprint for x. If so, we say that x is (probably) in the table. If not, we say that x is (definitely) not in the table.

It's helpful to compare this idea against a Bloom filter. With a Bloom filter, we hash x to a number of positions, then derive a value from those positions by AND-ing everything together, and finally check if the value we got was equal to 1. With an XOR filter, we hash x to three positions, derive a value from those positions by XOR-ing them together, and finally check if the value we got is equal to f(x).

To change the false positive rate for the XOR filter, we simply change the value of L. Specifically, the likelihood that f(x) coincidentally happens to match the XOR of the three locations given by h₁(x), h₂(x), and h₃(x) is 2^-L, since that's the probability that a random L-bit value matches another. Therefore, to get a false positive rate of ε, we simply set L = log₂ ε^-1.

The challenging part is filling in the table. It turns out that there's a really simple strategy for doing so. To store a list of n elements, create a table of size 1.23n. Then, use this recursive procedure:

If there are no items left to place, you're done.
Pick an item x with the following property: x hashes to a table slot (say, slot k) that no other items hash to.
Remove x from the list of items to place and recursively place the remaining items.
Set the value of slot k to a number such that the XOR of the table slots x hashes to equals f(x). (This is always possible: simply XOR together the contents of the other two table slots and f(x), then store that in slot k.)

This procedure has a slight chance of getting stuck in step (2) if every table slot has at least two items hashing to it, but it can be shown that as long as you use at least 1.23n table slots the probability that this occurs is extremely small. If that happens, simply choose new hash functions and try again.

XOR filters have several advantages over regular Bloom filters.

To decrease the false positive rate of a Bloom filter, we have to add in more functions. Specifically, for an error rate of ε, we need to use log₂ ε^-1 hash functions. On the other hand, an XOR filters always use exactly three hash functions.
As a consequence of this, lookups in a Bloom filter typically are slower than in an XOR filter, since each table slot probed is essentially in a random location and probably causes a cache miss. With Bloom filters, we have log₂ ε^-1 cache misses per item. With XOR filters, we have three cache misses per item.
Bloom filters use more space. A Bloom filter with error rate ε needs a table of size 1.44n log₂ ε^-1. An XOR filter has an array of 1.23n items, each of which is log₂ ε^-1 bits long, for a total space usage of 1.23n log₂ ε^-1.

XOR filters have one main disadvantage relative to Bloom filters, and that's that all the items to store in the XOR filter must be known in advance before the filter is constructed. This contrasts with Bloom filters, where items can be added incrementally over a long period of time. Aside from this, though, the XOR filter offers better performance and memory usage.

For more information about XOR filters, along with how they compare in terms of time and space to Bloom filters and cuckoo filters, check out this set of lecture slides, which explains how they work, along with where the 1.23 constant comes from and why we always use three hash functions.