Part 9: Quotient Filters - Removing Values

In the previous article of this series, we saw how to add values to a Quotient Filter; now let's see how to remove some. 

---

Removing a Value from a Quotient Filter - Examples

Let's see how to remove values from a QF. Interestingly, the examples we saw for additions in the previous sections will work now for removals, but in reverse! (See question 11½–8 for more on this.) We will just go over the earlier examples again, but in reverse. First, let's remove A for q=2.

Figure 11½–15: Removing a value at the end of a run and a cluster

After checking that the run exists for q=2 (isOcc is set) we find the start of the run. As isShifted is not set, the run begins right there. The next slot is empty (isCont is not set) so the run ends after one element, and there is nothing to shift. To remove the value, we clear the remainder, and reset isOcc; the other metadata bits are already unset.

Now let's see how we'd remove H in the middle of a cluster. Also, the value is the only one in its run; we'll see an example with a longer run after this one.

Figure 11½–16: Removing a value from the start of a run, at the middle of a cluster

After checking that the run for q=6 exists, we find the corresponding cluster; occupied quotients from slot 4 (the beginning of the cluster) up to 6 are 4, 5, and 6, and the runs start at positions 4, 8, and 10. We scan the run for q=6, find the match, and since slot 11 has isCont not set, we just remove H by shigetting to the main logic, let's seefting the rest of the cluster leftward. As the run had a single element, we clear isOcc.

For a final case, let's remove something from the middle of a run; we want to delete the value for q=5 and remainder C. (Remember, we deliberately had a repeated remainder to show that remainders are not unique.) The following figure shows the case.
isShifted

Figure 11½–17: Removing a value from the middle of a run

Here we proceed the same way, and after finding the run and the remainder in it, we shift the remaining cluster elements left. Here the run still has other values (B and D) so isOcc remains set. After the shift, the last slot in the cluster becomes empty. The removed element wasn't the head of the run, so no new head gets isCont unset. Had B been removed instead, C would have become the head of the run, with isCont unset.

Removing a Value from a Quotient Filter - Implementation

In essence, removing a value is similar to adding one. First, verify whether the value is in the QF; if it is, shift all following items backward, possibly fixing some metadata bits. Before the main logic, let's look at an auxiliary function, clusterRunQuotients, which we'll use later. This function receives the first slot of a cluster and returns the home slots (quotients) of all the runs stored in that cluster, in table order.

const clusterRunQuotients = (qf, slot) => {
➊const quots = [];

➋for (
    let is1stPass = true;
    !isSlotEmpty(qf, slot) &&
    (is1stPass || qf.slots[slot].isShifted);
➌  slot = wrapSlot(qf, slot + 1), is1stPass = false
  ) {
➍  if (qf.slots[slot].isOcc) {
      quots.push(slot);
    }
  }

  return quots;
};

The quots array ➊ will collect the quotients found when starting from slot. We have a loop (which I wrote using for(...) just for variety; a while would also have done well) that starts ➋ at the run's first slot and moves forward. The loop continues only while the current slot is not empty (because a cluster is a contiguous group of used slots) and it is either the first slot, or the slot is shifted; an unshifted entry sits in its own home slot, beginning a new cluster. After the test ➌ we advance and reset the is1stPass flag. In the loop ➍ we push the slot number whenever we find isOcc set.

When we are done, the k-th element in the returned array is the home slot for the k-th run in the cluster; we'll use this to know which run each shifted entry belongs to. Now we can get to the main remove code.

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

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

➌const clusterStart = findClusterStart(qf, quot);
  const runStart = locateRun(qf, quot);

  let target = runStart;

➍for (;;) {
    if (
      isSlotEmpty(qf, target) ||
      (target !== runStart && !qf.slots[target].isCont) ||
      qf.slots[target].rem > rem
    ) {
      return false;
    }

➎  if (qf.slots[target].rem === rem) {
      break;
    }
    target = wrapSlot(qf, target + 1);
  }

➏const wasRunStart = target === runStart;
  const nextSlot = wrapSlot(qf, target + 1);
  const hasMoreOfSameRun =
    !isSlotEmpty(qf, nextSlot) && qf.slots[nextSlot].isCont;

➐const runQuotients = clusterRunQuotients(qf, clusterStart);
  let currentRunIndex = runQuotients.indexOf(quot);

➑if (wasRunStart && !hasMoreOfSameRun) {
    qf.slots[quot].isOcc = false;
  }

➒shiftLeftAndRemove(
    qf,
    target,
    runQuotients,
    currentRunIndex,
    wasRunStart,
    hasMoreOfSameRun
  );

  return true;
};

The goal of the code is to delete one copy of an item's remainder from its run, then close the gap by sliding the rest of the cluster one slot to the left. We find the quotient and remainder ➊ and if the slot is empty ➋ we know that the item cannot be in the filter, so there's nothing to do. We find the start of the cluster ➌ and the start of the run for the quot run. We scan the run from its beginning ➍ looking for the remainder. We know the search was unsuccessful in three cases: if the slot is empty, if we've entered another run, or if the stored remainder is greater than the one we seek, so ours cannot appear later. An equal remainder ➎ means we found the slot to delete, called target.

We record ➏ two facts about the deleted element's situation, which we'll need to decide whether some metadata bits need fixing: whether it was the first element of its run, and whether the next slot continues the same run. Next ➐ runQuotients is the ordered list of home slots of all runs in the cluster, and currentRunIndex is the position of our run in it. During the shift, this lets us work out whether each moved element ends up in its home slot. It is computed before anything changes. If we are deleting the only element in the run ➑ the run disappears, so the home slot's isOcc bit is cleared. Finally ➒ shiftLeftAndRemove closes the gap, and we return true.

Doing the shifting and bit handling is in a separate function, as for add.

const shiftLeftAndRemove = (
  qf,
  slot,
  runQuotients,
  currentRunIndex,
  wasRunStart,
  hasMoreOfSameRun
) => {
  let is1stIteration = true;
  for (;;) {
    const next = wrapSlot(qf, slot + 1);

➊  if (isSlotEmpty(qf, next) || !qf.slots[next].isShifted) {
➋    qf.slots[slot].rem = 0;
      qf.slots[slot].isOcc = false;
      qf.slots[slot].isCont = false;
      qf.slots[slot].isShifted = false;
      qf.c--;
      return;
    }

➌  if (!qf.slots[next].isCont) {
      currentRunIndex++;
    }

➍  let continuationToWrite = qf.slots[next].isCont;
    if (is1stIteration && wasRunStart && hasMoreOfSameRun) {
      continuationToWrite = false;
    }

➎  qf.slots[slot].rem = qf.slots[next].rem;
    qf.slots[slot].isCont = continuationToWrite;

    if (!continuationToWrite) {
      qf.slots[slot].isShifted =
        slot !== runQuotients[currentRunIndex];
    } else {
      qf.slots[slot].isShifted = true;
    }

➏  slot = next;
    is1stIteration = false;
  }
};

This function overwrites the deleted slot with its successor, then repeats with that successor's slot, and so on down the cluster. Before pulling the next slot in ➊ we check whether it should move. If it is empty, or its isShifted bit is false, it is in its own home slot and marks the start of a new cluster, so it must not move. The current slot is then the last one of the shifted tail. The last slot is wiped ➋ by clearing all three flag bits, and the item count qf.c is decremented. The isOcc bit is also cleared here, which is safe because no run can have its home at a slot whose successor is the start of a new cluster. If the successor is not a continuation ➌ it begins a new run, so we advance currentRunIndex to that run's home slot. When the deleted element was the only one in its run, this also skips past the vanished run correctly. We decide the continuation bit to write ➍; normally it is the successor's own, but the exception is the very first iteration when we deleted a run start that has more elements: the successor becomes the new first element of the run, so its isCont is forced to false. The remainder and continuation bit are copied into the current slot ➎ and isShifted is recomputed: a continuation element is always shifted, and a run-start element is shifted only if its new slot differs from its run's home slot, since moving left may put it exactly at home. Finally ➏ the loop moves on to the slot we just copied from, and the first-iteration special case no longer applies.

We're done! We can move on to a better-performing filter, Cuckoo Filters, which are also related to hash tables with buckets, as we'll see.

---

Bye for now! In the next article in the series, we will study Cuckoo Filters, which have some performance advantages in terms of speed and memory needs.

---

Questions

11½–8. It all comes out in the wash. For a QF, does the order in which we add values affect its final configuration? What happens if we also consider removals?