Fusion Tree - Parallel Comparison

Parallel Comparison

The purpose of the compression achieved by sketching is to allow all of the keys to be stored in one w-bit word. Let the node sketch of a node be the bit string

1sketch(x₁)1sketch(x₂)...1sketch(x_k)

We can assume that the sketch function uses exactly b ≤ r4 bits. Then each block uses 1 + b ≤ w4/5 bits, and since k ≤ w1/5, the total number of bits in the node sketch is at most w.

A brief notational aside: for a bit string s and nonnegative integer m, let sm denote the concatenation of s to itself m times. If t is also a bit string st denotes the concatenation of t to s.

The node sketch makes it possible to search the keys for any b-bit integer y. Let z = (0y)k, which can be computed in constant time (multiply y by the constant (0b1)k). Note that 1sketch(x_i) - 0y is always positive, but preserves its leading 1 iff sketch(x_i) ≥ y. We can thus compute the smallest index i such that sketch(x_i) ≥ y as follows:

1. Subtract z from the node sketch.
2. Take the bitwise AND of the difference and the constant (10b)k. This clears all but the leading bit of each block.
3. Find the most significant bit of the result.
4. Compute i, using the fact that the leading bit of the i-th block has index i(b+1).