to keys in constant time. This is done by compressing ("sketching") the keys so that all can fit into one machine word, which in turn allows comparisons to be done in parallel. So, a series of computations involving sketching, parallel comparison and most significant bit index locator, help reach the required solution. Sketching Sketching is the method by which each -bit key at a node containing keys is compressed into only bits. Each key may be thought of as a path in the full binary tree of height starting at the root and ending at the leaf corresponding to . This path can be processed by recursively searching the left child of i if the ith bit is 0, and the right child if it is 1, generally, until all bits are scanned. To distinguish two paths, it suffices to look at their branching point (the first bit where any two keys differ). As there are a maximum of k keys, there will not be more than k-1 branching points, which means that no more than k-1 bits are required to identify a key. And hence, no sketch will have more than k-1 bits. An important property of the sketch function is that it preserves the order of the keys. That is, for any two keys . So, for the entire range of keys, sketch(x0)<sketch(x1)<...<sketch(xk-1) because if the binary tree like path is followed the nodes will be ordered in such a manner that x0<x1<...<xk-1. Approximating the sketch If the locations of the sketch bits are b1 < b2 < ··· < br, then the sketch of the key xw-1···x1x0 is the r-bit integer . With only standard word operations, such as those of the C programming language, it is difficult to directly compute the perfect 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, called the approximate sketch, which does have all the important bits but also some additional useless bits spread out in a predictable pattern. The bitwise AND operation serves as a mask to remove all these non-sketch bits from the key, while the multiplication shifts the sketch bits into a small range. Like the "perfect" sketch, the approximate sketch also preserves the order of the keys and means that sketch(x0)<sketch(x1)<...<sketch(xk-1). Some preprocessing is needed to determine the correct