Quotient Filters - Creating and Searching

In the previous article of this series, we saw how a Quotient Filter is used. Here we'll see how to size and search those filters, with actual code.

---

Creating a Quotient Filter

Before we look at the code for creating a QF, let's work out what its parameters should be. Suppose we want to add n values to a QF with an α false-positive rate below ε and a load factor below α. (Why the latter? A QF is similar to a hash table in some ways, and the higher the load factor, the slower all operations are. We might want α below 0.75, for example.) How should we size the QF?

• We need n/s < α and s = 2^q because we want the table length to be a power of 2. This leads to q = ⌈log₂(n/α)⌉, our first result.
• A query for a key that isn't in the set gives a false positive only if its p-bit fingerprint matches one of the n stored fingerprints. For a uniform hash, each stored key matches with probability 2^‑p. Since we want this to be lower than ε, p = ⌈log₂(n/α)⌉ and then r = p‑q.

Given these results, we can now show how to create a QF.

const EPSILON = 0.01;
const ALPHA = 0.75;

const createQuotientFilter = (n, eps = EPSILON) => {
➊const p = Math.ceil(Math.log2(n / eps));
  const q = Math.ceil(Math.log2(n / ALPHA));
  const r = p - q;
  const s = 1 << q;
  const c = 0;    // number of values in the QF

➋return {
    p,
    q,
    r,
    s,
    c,
➌  slots: Array.from({ length: s }, () => ({
      rem: 0,
      isOcc: false,
      isCont: false,
      isShifted: false
    }))
  };
};

First, we do the calculations ➊ as shown before; a good idea is to add defensive checks to avoid wrong parameters. For us ➋ a QF will be an object with all the dimensions ( p, q, r, and s ) and c to count how many values are in the QF; we will want to avoid overloading the structure with too many values. Finally ➌ the slots array includes the rem field to store the remainders, and the three metadata bits we described previously. (See question 11½–5 for a possible, but incorrect, way to simplify the code.)

We will also introduce the fingerprint function, which depends on the calculated values for p, q, and r. We will use the hashWithSeed function from earlier articles to produce an array with quotient and remainder.

const fingerprintOf = (qf, item) => {
  const hash = hashWithSeed(String(item), 0);
  return [
➊ (hash & ((1 << qf.p) - 1)) >>> qf.r,
➋  hash & ((1 << qf.r) - 1)
  ];
};

The bitwise operations simplify the work: 

• the quotient is found ➊ by first masking out all bits except the rightmost p ones, and then shifting right to drop r bits, leaving just q bits, and
• the remainder is found ➋ by masking out all bits except the rightmost r ones.

We can now create a QF; let's work out how to search it, as described in the previous article.

Searching a Quotient Filter

Let's see the code to find a value. To make the logic clearer, we'll be using a few auxiliary functions that will also come in handy for other operations on a QF.

➊ const wrapSlot = (qf, slot) => (slot + qf.s) % qf.s;

➋ const isSlotEmpty = (qf, slot) =>
  !qf.slots[slot].isOcc &&
  !qf.slots[slot].isCont &&
  !qf.slots[slot].isShifted;

First ➊ we need a function to avoid going out of the array bounds when moving forwards or backward, taking into account that we are wrapping around; the calculation used takes any index (even -1) and forces it into the correct range. We will also write a function to determine if a slot is totally empty ➋ by checking if all its metadata bits are unset. With these two functions under our belt, we can now do a search.

const find = (qf, item) => {
➊  const [quot, rem] = fingerprintOf(qf, item);

➋  if (!qf.slots[quot].isOcc) {
      return false;
    }

➌  const runStart = locateRun(qf, quot);
    let slot = runStart;
➍  while (true) {
      if (
➎      isSlotEmpty(qf, slot) ||
➏      (slot !== runStart && !qf.slots[slot].isCont) ||
➐      qf.slots[slot].rem > rem
      ) {
      return false;

➑  } else if (qf.slots[slot].rem === rem) {
      return true;

    } else {
➒    slot = wrapSlot(qf, slot + 1);
    }
  }
};

To start the search ➊ we find the fingerprint for the sought value, a quotient and remainder, and if there were no values for that quotient ➋ we know the value isn't present. We use an auxiliary runStart function ➌ to find the first slot in the run that contains the quotient; we'll see it below. After that ➍ we start walking forward. If we reach an empty slot ➎ we walk past the end of the current run ➏, or we are at the right run but exceeding the sought remainder ➐ then the search fails. (For an important detail, see question 11½–6.) If we find the expected remainder ➑ the search succeeds, and in other cases ➒ we just keep advancing.

In the add function, we ensure the table is never 100% full; otherwise, we'd need checks to avoid looping back to the start of the search. (In fact, we'll force its load factor to always be below α to ensure good performance.) Now, let's see the locateRun function.

 

 ➊const findClusterStart = (qf, slot) => {
  while (qf.slots[slot].isShifted) {
    slot = wrapSlot(qf, slot - 1);
  }
  return slot;
};

const locateRun = (qf, quot) => {
➋let clusterStart = findClusterStart(qf, quot);
  let runNumber = 0;
  let slot = clusterStart;
  while (true) {
➌  if (qf.slots[slot].isOcc) runNumber++;
➍  if (slot === quot) break;
➎  slot = wrapSlot(qf, slot + 1);
  }

➏let runStart = clusterStart;
  for (
    let currentRun = 1;
    currentRun < runNumber;
    currentRun++
  ) {
    do {
➐    runStart = wrapSlot(qf, runStart + 1);
➑  } while (qf.slots[runStart].isCont);
  }

➒return runStart;
};

First ➊ we have a findClusterStart that just looks for the start of the cluster that includes a given slot; it just goes backward until it reaches a slot with the isShifted bit unset. Now we can study locateRun. After determining the cluster start ➋ it moves forward ➎ until reaching the target quotient slot. Every time it encounters an occupied slot ➌ it increments runNumber; on exiting the loop ➍ this variable tells us the ordinal number of the quotient's run within the cluster. (This is not the actual slot yet; it is only the count of occupied runs encountered before the target quotient.)

Now ➏ the function starts from the cluster start and advances through runs. The crucial things to remember are that a run may contain multiple occupied slots, and continuation slots have isCont set, so the code skips those slots ➐ until it reaches the first one of the next real run ➑. At the end ➒ runStart is the first slot of the run associated with quot as we wished.

---

Bye for now! In the next article in the series, we will study how to maintain Quotient Filters, by adding and removing values.

---

Questions

11½–5. Why not make it simpler? We could have written the return in the createQuotientFilter function as follows; why would it have been a bad idea?

  return {
    p,
    q,
    r,
    s,
    c,
    slots: Array(s).fill({
      rem: 0,
      isOcc: false,
      isCont: false,
      isShifted: false
    })
  };

11½–6. Unneeded test? We know that the QF will never be full, so why do we need the test for slot !== runStart at ➐ in the find code?