multiplication constant. Each sketch bit in location bi will get shifted to bi + mi via a multiplication by m = 2mi. For the approximate sketch to work, the following three properties must hold: bi + mj are distinct for all pairs (i, j). This will ensure that the sketch bits are uncorrupted by the multiplication. bi + mi is a strictly increasing function of i. That is, the order of the sketch bits is preserved even in x'.m. (br + mr) - (b1 + m1) ≤ r4. That is, the sketch bits are packed into a range of size at most r4, where r ≤ O(w1/5). An inductive argument shows how the mi can be constructed. Let m1 = w − b1. Suppose that 1 < t ≤ r and that m1, m2... mt-1 have already been chosen. Then pick the smallest integer mt such that both properties (1) and (2) are satisfied. Property (1) requires that mt ≠ bi − bj + ml for all 1 ≤ i, j ≤ r and 1 ≤ l ≤ t-1. Thus, there are less than tr2 ≤ r3 values that mt must avoid. Since mt is chosen to be minimal, (bt + mt) ≤ (bt-1 + mt-1) + r3. This implies Property (3). The approximate sketch is thus computed as follows: Mask out all but the sketch bits with a bitwise AND between x and . Multiply the key by the predetermined constant m as calculated above. This operation actually requires two machine words, but this can still be done in constant time. Mask out all but the shifted sketch bits. These are now contained in a contiguous block of at most r4 < w4/5 bits. 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(x1)1sketch(x2)...1sketch(xk) Here, all sketch words are clubbed together in one string by prepending a set bit to each of them. 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