The counterexample

Four keys with w = 4 (22:02):

KeySketch (bits 0 and 3, read from the left)
000000
001001
110010
111111
  • Two branch bits: the 0th and 3rd bits from the left (22:22, 24:30).
  • Query q = 0101 has sketch(q) = 00 (24:55, 25:25).
  • Truth: q belongs between 0010 and 1100. Sketch says: it sits at the very bottom, between the first two keys (25:25, 25:52).
  • Formally: sketch(q) between sketch(x_i) and sketch(x_{i+1}) does not imply q is between x_i and x_{i+1} (27:25).
  • Cause: q branched off at a position that is not a stored branch bit, so the sketch lost the information (27:03).

The fix: build a surrogate key e

Let y be the node (trie prefix) where q first falls off the highlighted paths (28:15). Two cases:

  • q falls off to the right → e = y · 0 · 111...1 (y, then a 0, then all ones) (29:21, 29:56).
  • q falls off to the left → e = y · 1 · 000...0 (29:56).

Claim: where sketch(e) falls among the sketch(x_i) is the same as where q falls among the x_i — which is what we actually want (29:56, 31:43). The proof is left as an exercise (33:40).

The resulting two-pass query procedure

  1. Run the parallel comparison of sketch(q) against the stored sketches to find where it lands (32:10).
  2. Use the two neighbours found to form e.
  3. Run the comparison again with e; that second result determines which subtree to descend into (32:10).

Finding y with MSB and XOR

  • x_i XOR q marks exactly the bits where the two differ; its most significant set bit is the first bit where they diverge (34:08).
  • The XOR is applied to the actual x_i (which are stored in full), not to the sketches (34:37, 41:03).
  • Compute MSB(x_i XOR q) and MSB(x_{i+1} XOR q), then take the more significant of the two — that gives the first place q falls off between the two neighbours (34:54).
  • This is why constant-time MSB (topic 10) is a prerequisite (35:34).

Ties

  • When sketch(e) equals one of the stored sketches there are only two candidate positions left, so a direct comparison against x_i and x_{i+1} resolves it (45:02, 45:37, 45:54).
flowchart TD
    Q["query q arrives at node"] --> S1["sketch(q) — O(1) via mask, multiply, mask, shift"]
    S1 --> P1["parallel compare vs stored sketches → candidate neighbours x_i, x_{i+1}"]
    P1 --> M["y = more significant of MSB(x_i XOR q), MSB(x_{i+1} XOR q)"]
    M --> E{"q fell off..."}
    E -->|right| ER["e = y·0·111…1"]
    E -->|left| EL["e = y·1·000…0"]
    ER --> P2["parallel compare with e"]
    EL --> P2
    P2 --> D["correct subtree to recurse into"]