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), to make it as long as the node sketch such that each word in the node sketch can be compared with the query integer y in one operation, demonstrating word-level parallelism. If y were 5 bits long, it would be multiplied by 000001....000001 to get sketch(y)k. The difference between sketch(xi) and 0y results in the leading bit for each block to be 1, if and only if sketch(y) sketch(xi). We can thus compute the smallest index i such that sketch(xi) ≥ y as follows: Subtract z from the node sketch. Take the bitwise AND of the difference and the constant (10b)k. This clears all but the leading bit of each block. Find the most significant bit of the result, to identify the exact index of transition from elements with sketch smaller than the query sketch to those greater than the query sketch. Compute i, the rank of the sketch, using the fact that the leading bit of the i-th block has index i(b+1). Desketching For an arbitrary query q, parallel comparison computes the index i such that sketch(xi-1) ≤ sketch(q) ≤ sketch(xi) Unfortunately, this does give the exact predecessor or successor of q, because the location of the sketch of q among the sketches of all the values may not be the same as the location of q in all the actual values. What is true is that, among all of the keys, either xi-1 or xi has the longest common prefix with q. This is because any key y with a longer common prefix with q would also have more sketch bits in common with q, and thus sketch(y) would be closer to sketch(q) than any sketch(xj). The length longest common prefix between two w-bit integers a and b can be computed in constant time by finding the most significant bit of the bitwise XOR between a and b. This can then be used to mask out all but the longest common prefix. Note that p identifies exactly where q branches off from the set of keys. If the next bit of q is 0, then the