Why masking alone is not enough

  • Masking with a precomputed word isolates the branch bits with one bitwise AND (38:01, 38:35).
  • But the result still occupies w bits, so w^(1/5) keys still need w^(6/5) bits of space — no compression at all (38:35, 39:27).
  • Preprocessing could build perfect r-bit sketches for the stored x_i, but q arrives online, so the sketch operation must be applicable to q in constant time too (40:24, 40:43, 41:03).

The relaxation: approximate sketches

  • Perfect compression would reach r bits; instead settle for r^4 bits, with a known amount of 0-spacing between the important bits (38:53, 39:27).
  • Why r^4 is acceptable: r^5 = w, so r^4 = w^(4/5) < w — the compression from a width of w down to w^(4/5) is what makes the node fit (38:53, 53:31, 53:51).
  • This is why k = w^(1/5) was chosen — the exponent budget comes out of this lemma (37:37).
  • Both the x_i and their sketches are stored; sketches could equally be recomputed on the fly, and storing them is still linear space (41:17, 41:32, 41:49).

The multiplication idea

Take x already masked to its important bits, x = Σ_{i=0..r-1} x_{b_i} · 2^{b_i}, and a multiplier m = Σ_i 2^{m_i} with exactly r one-bits (45:54, 47:05).

Then x · m = Σ_i Σ_j x_{b_i} · 2^{b_i + m_j} — r² cross terms (49:08).

The b_i are increasing; the m_i are arbitrary, not necessarily increasing or a permutation of the b_i (47:25, 54:24).

The lemma

There exist m_i such that (47:25, 48:09, 48:42):

  • (a) all r² sums b_i + m_j are distinct (48:09);
  • (b) the diagonal sums are increasing: b_0 + m_0 < b_1 + m_1 < ... < b_{r-1} + m_{r-1} (48:09);
  • (c) the spread is small: (b_{r-1} + m_{r-1}) - (b_0 + m_0) = O(r^4) (48:42).

Why each property matters:

  • (a) guarantees no two terms share a power of 2, so there are no carries to corrupt the product (49:41).
  • Only the r diagonal positions b_i + m_i are read; bit x_{b_i} is recovered from the power of 2 at b_i + m_i (49:41, 52:42). This is why (b) only constrains the i = j terms (52:20).
  • (c) bounds the surviving bits inside a window of width r^4, so a shift brings them down to a contiguous low-order block (50:17, 51:25, 51:39).

Note: x and m are full w-bit words with only r nonzero bits each; b_i ≤ w and m_i ≤ w², so b_i + m_i is not bounded by 2r (51:01, 51:39).

The sketch algorithm — 4 operations, O(1)

  1. Mask x down to the branch bits b_i (mask precomputed) (54:48, 54:05).
  2. Multiply by m (found in preprocessing) (54:48).
  3. Mask out everything except the r positions b_i + m_i (54:24, 54:48).
  4. Shift right by b_0 + m_0 so the block starts at the least significant bit (55:43).

Result: a sketch fitting in r^4 bits, computed with a mask, a multiplication, another mask, and a shift — four word operations, so O(1), and applicable to an online query q (1:03:15, 1:03:39, 55:43).