Part 8: Quotient Filters - Adding Values

In the previous article of this series, we saw how to create and search a Quotient Filter; now let's see how to add values. This article will be longer than usual, but that's because we'll have plenty of code; no way around that!

Adding a value to a Quotient Filter - Examples

We can now see how to add a value to a QF. First, let's see a few examples so we can better understand the logic we'll write. For clarity, in all cases we'll start with the setup we saw in previous parts, and show a single update.

The first case is the simplest one; see figure 11½–12. We add a value with a quotient, A, that hasn't appeared yet, and its slot is empty. In that case, we just occupy the slot and set its isOcc bit to 1; isCont and isShifted stay at 0 because A is the first element of a run and it's in its home slot. The figure below shows this situation; involved items have thick borders, and changed values have a grey background.

Figure 11½–12: The simplest addition is when the home slot is empty, available.

What happens if we add a new run but the slot is occupied? Figure 11½–13 shows this situation; the new remainder, H, is for q=6.

Figure 11½–13: Here we add a new run not at its home slot, and have to displace other items.

In this case, we needed several changes:

isOcc becomes 1 at slot #6, because now we have one run for that quotient.
H is stored at slot 10, right after the end of the run for q=5 and before the beginning of the run for q=7. It has isCont set to 0 because it starts a run, and isShifted set to 1 because it's not at the home slot.
elements after H in the same cluster are moved right; this involves C, F, and H, and their values for rem, isCont, and isShifted are displaced.

Let's just see one more example, adding something somewhere in an existing run; in this case, we'll add remainder C to q=5. (And, yes, remember the same remainder may appear for different quotients; I wanted to specifically show a case of this.) Figure 11½–14 shows how it would go.

Figure 11½–14: Adding a new value to an existing run.

In this case:

isOcc[5] doesn't change because it was already 1
the new value goes between B and D so the former stays in place; the head of the run doesn't change in this example
all the rest of the items in the cluster starting at D onwards move forward (with their isCont and isShifted bits unchanged) to open space for C as a continuation (isCont=1) and displaced (isShifted=1)

Inserting the value at the end of a run (say, remainder I for q=5) would have been very similar. Adding remainder W to q=15 would also work in the same way, except for the wrapping around.

In essence, the examples above cover all the possibilities; we can now move on to actual JavaScript code.

Adding a value to a Quotient Filter - Implementation

Now, let's get to the code. As we saw earlier, the issue is determining where the new value should fit, possibly displacing other items forward to make space. The code is a bit longish; see below.

const add = (qf, item) => {
➊if (qf.c + 1 > qf.s * ALPHA) {
    throw new Error("Quotient filter load limit reached");
  }

➋const [quot, rem] = fingerprintOf(qf, item);

➌if (isSlotEmpty(qf, quot)) {
    const slot = qf.slots[quot];
    slot.rem = rem;
    slot.isOcc = true;
    qf.c++;
    return;
  }

➍const runAlreadyExists = qf.slots[quot].isOcc;
  qf.slots[quot].isOcc = true;
➎const runStart = locateRun(qf, quot);

  let insertAt;
  let is1stOfRun;
  if (runAlreadyExists) {
    let slot = runStart;

➏  while (true) {
      if (
➐      isSlotEmpty(qf, slot) ||
        (slot !== runStart && !qf.slots[slot].isCont) ||
        qf.slots[slot].rem >= rem
      ) {
        break;
      }

      slot = wrapSlot(qf, slot + 1);
    }

➑  insertAt = slot;
    is1stOfRun = insertAt === runStart;
  } else {
➒  insertAt = runStart;
    is1stOfRun = true;
  }

➓shiftRightAndInsert(
    qf,
    insertAt,
    rem,
    !is1stOfRun,
    insertAt !== quot,
    runAlreadyExists && is1stOfRun
  );
};

As we mentioned earlier, we don't want the QF to get too full, so we do not allow an insertion ➊ if the table load factor would become too high; this bounds how long runs and clusters get. (Also, if the table could be full, the algorithms we would need extra checks to avoid infinite loops.)

After that check ➋ we find the fingerprint (quotient and remainder) for the value, and check for the "fast path". If the home slot is empty ➌ we just store the remainder there, set the metadata bits, and we're done! Otherwise, the canonical slot is in use, either by this quotient's run or by another entry shifted in from elsewhere.

The slot's isOcc flag says whether a run for this quotient already exists ➍. That value is saved in runAlreadyExists before the flag is forced to true, because the quotient will have a run after this insertion either way, and the old value is still needed below. Now ➎ we find the slot where the run for quot starts. If the run doesn't exist yet, we get the slot where the new run should begin. We now have to find where the new remainder should go ➏ keeping its run in ascending order. We will be done in this search ➐ when either:

the slot is empty, so the run ended exactly at the edge of the occupied cluster, and the item can go there with nothing to move.
the slot is not the run's start and is not a continuation: it belongs to the next run, so the current run has ended, and the item goes at its end.
the stored remainder is greater than or equal to the new one, so we know where to insert it. (See question 11½–7 for more on this.)

In any of these cases ➑ insertAt is the final slot. Here, is1stOfRun is true only when the insertion point is the run's first slot, meaning the new remainder is the smallest in the run. If the item landed later in the run or just past its end, it is not the first. If no run existed ➒ the new run starts instead at the location from ➎, and the item is by definition its first member.

The final step ➓ shifts slots right to finish the work. The shiftRightAndInsert function receives the remainder and three flags, and does the needed insertion:

!is1stOfRun becomes the continuation bit. Anything that is not the first of its run is a continuation.
insertAt !== quot becomes the shifted bit. The item is shifted if it ends up away from its canonical slot.
runAlreadyExists && is1stOfRun is the "force next continuation" flag. It applies when the new item becomes the head of an existing run. The old head, which is displaced one slot to the right, must then be marked as a continuation. If the run is new, this is false, and whatever is displaced keeps its status, since it belongs to a different run.

We're almost done! The shiftRightAndInsert function is also a bit longish. Its job is to shift elements forward, making space to add the new remainder.

const shiftRightAndInsert = (
  qf,
  slot,
  rem,
  continuationFlag,
  shiftedFlag,
  forceNextContinuation
) => {
➊let carryRem = rem;
  let carryContinuation = continuationFlag;
  let carryShifted = shiftedFlag;
  let is1stIteration = true;

➋for (;;) {
➌  if (isSlotEmpty(qf, slot)) {
      qf.slots[slot].rem = carryRem;
      qf.slots[slot].isCont = carryContinuation;
      qf.slots[slot].isShifted = carryShifted;
➍    qf.c++;
      return;
    }

➎  const displacedRem = qf.slots[slot].rem;
    let displacedContinuation = qf.slots[slot].isCont;

➏  if (is1stIteration && forceNextContinuation) {
      displacedContinuation = true;
    }

➐  qf.slots[slot].rem = carryRem;
    qf.slots[slot].isCont = carryContinuation;
    qf.slots[slot].isShifted = carryShifted;

➑  carryRem = displacedRem;
    carryContinuation = displacedContinuation;
    carryShifted = true;

➒  slot = wrapSlot(qf, slot + 1);
    is1stIteration = false;
  }
};

The function works like a bucket brigade; at any moment ➊ it holds one "carried" entry: a remainder plus its continuation and shifted metadata bits. Initially, the carried entry is the new item, plus the bits that were determined by add, and is1stIteration is needed later for a special case. A forever loop ➋ starts, which ends only ➌ when the carried entry lands in an empty slot and ➍ the element count is updated.

When moving forward, if an occupied slot is found ➎ its current remainder and continuation bit are saved before being overwritten. This is the entry that will move one slot right. On the first iteration only, if forceNextContinuation is set ➏ the displaced entry's continuation bit is forced to true. This covers the case when a new item takes over the head of an existing run, while the old head becomes the second element of the run, a continuation. (Later displaced entries keep their own continuation bits, since their position within their runs doesn't change.) The slot ➐ receives the carried remainder and metadata. (For the first slot these are the values chosen by add, and for later slots they are the values of the displaced entry.) Then ➑ the displaced entry becomes the new carried entry, always having its shifted bit to true, because it gets moved from its original place, which can no longer be its canonical slot. Finally ➒ the loop advances to the next slot, clearing the first iteration flag so the rule at ➏ won't fire again.