Doubly-Logarithmic Time

XFastTrie: Searching in doubly-logarithmic Time

The performance of the BinaryTrie structure is not very impressive. The number of elements, $n$, stored in the structure is at most $2^w$, so $\log n \leq w$. In other words, any of the comparison-based SSet are at least as efficient as a BinaryTrie, and are not restricted to only storing integers.

Next, we describe the XFastTrie, which is just a BinaryTrie with $w + 1$ hash tables—one for each level of the trie. These hash tables are used to speed up the find(x) operation to $O(\log w)$ time. Recall that the find(x) operation in a BinaryTrie is almost complete once we reach a node, u, where the search path for x would like to proceed to u.right (or u.left) but u has no right (respectively, left) child. At this point, the search uses u.jump to jump to a leaf, v, of the BinaryTrie and either return v or its successor in the linked list of leaves. An XFastTrie speeds up the search process by using binary search on the levels of the trie to locate the node u.

To use binary search, we need a way to determine if the node u we are looking for is above a particular level, i, or if u is at or below level i. This information is given by the highest-order i bits in the binary representation of x; these bits determine the search path that x takes from the root to level i.

Visual demonstration of the search path

A visual demonstration of the search path is shown below: