Part 6: Quotient Filters - the Theory

In the previous articles of this series, we saw Bloom Filters, with restrictions on removing added values. Here we'll see Quotient Filters, which free the caller from those limits.

---

Quotient Filters

Bloom Filters answer one question cheaply: "Have I possibly seen this value before?" An SBF cannot support removals, and a CBF can, albeit at a cost: it requires more memory, and to ensure a removal causes no problems, the caller must do extra work. Quotient Filters (QF) work differently to avoid these issues.

A QF computes a single hash per item and splits it into two parts: a quotient that determines a slot in an array, and a remainder, which is stored in that slot as a small fingerprint. Because both the quotient and remainder come from a single source rather than several unrelated ones, the structure preserves enough information to support removals, using about the same memory as a comparable Bloom Filter.

Since the structure may be intimidating, let's start with an example of a built QF and how to search it, and we'll leave additions and removals for upcoming articles.

The Structure of Quotient Filters

A QF is, in some aspects, similar to a Hash Table with Open Addressing (see Chapter 11 for more on that) but there are some differences. In essence:

• Depending on how many values (n) you want to store, a size (s) is determined. Traditionally, the size is always a power of 2 so you can use bitwise operations for speed. A QF consists of s slots, each including content and three additional metadata bits. The table is used in circular fashion, so after the last element you loop back to the table's first.
• For each value to store, we compute a p-bit "fingerprint" hash, then split it into a q-bit quotient (such that 2^q = s) and an r-bit remainder; we have p = q + r. We will use the quotient as an index to determine the canonical/home slot where we would want to store the remainder. As with hash tables, the slot may already be in use, so we may need to move elements around. 

In a QF, all remainders corresponding to the same quotient will be stored contiguously, in ascending order, in one run. If we have two or more runs such that each one immediately follows the previous one, we call that sequence a cluster. Runs within a cluster appear in increasing order of their quotients.

You may be wondering how the structure works if we store only remainders. A good question, but we'll also have three metadata bits for each slot, and they will allow us to link each remainder (rem) to the corresponding quotient:

• isOcc[j] ("is occupied") is true if there is at least one value (stored somewhere in the table that corresponds to the quotient j.
• isCont[j] ("is continuation") is true if the element physically in slot j is not the first element of its run.
• isShifted[j] is true if the element at slot j is not in its own canonical slot; it had to be displaced.
• A totally empty, unused slot has its three metadata bits unset.

We've had several definitions; let's look at an actual QF and study how remainders and metadata bits work. Don't worry now about how the table was created; we'll get to that later.

An Example of Quotient Filters

A sample QF would look like the one shown in Figure 11½–11.

Figure 11½–11: A QF, with 4 runs in 12 slots. Slot for q=15 starts at the right and wraps around.

The size of a QF is usually a power of 2; here we have 16 slots, corresponding to q=4 bits. We are not showing actual remainders, but assume they require r=5 bits so we can show letters (A=1, B=2, C=3, etc.) to simplify. In our case, then p=9.

• After creating the empty QF, we added values E, G, K, and L for quotient 4; B and D for quotient 5; C, F, and W for quotient 7; and U, Y, and Z for quotient 15. In practice, the same remainder will often occur for different quotients, but to make the example clearer, we assume all remainders are distinct.
• The top row, slot #, just numbers the slots from 0 to 15. Remember that the table is circular, so slot 0 follows slot 15.
• The second row, isOcc, shows for which quotients there is at least one value. Positions 4, 5, 7, and 15 are set, and all the rest are not. 
• The third row, isCont, is set when the element corresponds to the same run as the immediately previous one.
• The last row, isShifted, shows whether the value is in its home slot.

Let's figure out the runs, and that will make everything clearer. 

• For quotient 4, isCont and isShifted are both 0, so the run starts at slot 4. Slots 5 through 7 have isCont set, so those three values are in the same run. The next slot (8) has isCont not set, so that's a different run. We conclude that the run for quotient 4 includes E, G, K, and L.
• For quotient 15, it's the same case. The only thing to keep in mind is that the table is circular, so the U at slot 15 is followed by Y and Z at slots 0 and 1.
• For quotient 5, isShifted is set, so the value there corresponds to a different quotient, not 5. To find the start of the run we want, we must first go back until we find a value with isShifted unset, which appears at slot 4. Then we move right along both the isOcc and isShifted rows, finding that the run for quotient 4 starts at slot 4, and the run for quotient 5 starts at slot 8. Now, moving right to slot 10, where isCont is not set, we deduce that the run for quotient 5 includes B and D.
• For quotient 7, the case is similar. Go left to the start of the run for quotient 4, then move right past the start of the run for quotient 5 at slot 8, and find the run for quotient 7 from slots 10 to 12, including C, F, and W.

Operations with a Quotient Filter

Now we can sketch how basic operations work; we'll see actual code in the following articles in this series. For starters, how do we search for a value? The logic is as follows:

• Use the hash function to determine the quotient and remainder for the value;
• Locate the run for that quotient; if there's no run, the value isn't in the QF.
• Start scanning the run for the remainder; if you find the value, the search was successful, but if you go past the end of the run or reach a value higher than your remainder, the search is unsuccessful.

To add a new value, the logic would run along the lines of:

• Use the hash function to determine the quotient and remainder for the value;
• If there is no run for that quotient and the corresponding slot is empty, just store the remainder there and set the metadata bits accordingly.
• If there's a run for that quotient, you'll have to locate it, determine where the new value should go, and "bump" the following values forward. This may force changing metadata for values in other runs.
• If there's no run for that quotient, you'll have to find the end of the previous run, move other values forward, and fix metadata bits.

Finally, removing a value requires:

• Find the corresponding run for the quotient and the slot for the remainder;
• Remove the value and move the following values to the left, fixing metadata bits if needed. 

These are just sketches; in the next article we'll cover creating and searching a QF, and then we'll look at the (longer, more complex) code for adding and removing values.

---

Bye for now! In the next article in the series, we will study how to size, create, and search Quotient Filters.