Fusion Tree - Approximating The Sketch

Approximating The Sketch

If the locations of the sketch bits are b₁ < b₂ < ··· < b_r, then the sketch of the key x_w-1···x₁x₀ is the r-bit integer .

With only standard word operations, such those of the C programming language, it is difficult to directly compute the sketch of a key in constant time. Instead, the sketch bits can be packed into a range of size at most r4, using bitwise AND and multiplication. The bitwise AND operation serves to clear all non-sketch bits from the key, while the multiplication shifts the sketch bits into a small range. Like the "perfect" sketch, the approximate sketch preserves the order of the keys.

Some preprocessing is needed to determine the correct multiplication constant. Each sketch bit in location b_i will get shifted to b_i + m_i via a multiplication by m = 2m_i. For the approximate sketch to work, the following three properties must hold:

1. b_i + m_j are distinct for all pairs (i, j). This will ensure that the sketch bits are uncorrupted by the multiplication.
2. b_i + m_j is a strictly increasing function of i. That is, the order of the sketch bits is preserved.
3. (b_r + m_r) - (b₁ - m₁) ≤ r4. That is, the sketch bits are packed into a range of size at most r4.

An inductive argument shows how the m_i can be constructed. Let m₁ = w − b₁. Suppose that 1 < t ≤ r and that m₁, m₂... m_t have already been chosen. Then pick the smallest integer m_t such that both properties (1) and (2) are satisfied. Property (1) requires that m_t ≠ b_i − b_j + m_l for all 1 ≤ i, j ≤ r and 1 ≤ l ≤ t-1. Thus, there are less than tr2 ≤ r3 values that m_t must avoid. Since m_t is chosen to be minimal, (b_t + m_t) ≤ (b_t-1 + m_t-1) + r3. This implies Property (3).

The approximate sketch is thus computed as follows:

1. Mask out all but the sketch bits with a bitwise AND.
2. Multiply the key be the predetermined constant m. This operation actually requires two machine words, but this can still by done in constant time.
3. Mask out all but the shifted sketch bits. These are now contained in a contiguous block of at most r4 < w4/5 bits.

For the rest of this article, sketching will be taken to mean approximate sketching.