We introduce and analyze a method to reduce the search cost in tries. Traditional trie structures use
branching factors at the nodes that are either fixed or a function of the number of elements. Instead,
we let the distribution of the elements guide the choice of branching factors. This is accomplished in
a strikingly simple way: in a binary trie, the i highest complete levels are replaced by a single node of
degree 2i; the compression is repeated in the subtries. This structure, the level-compressed trie,
inherits the good properties of binary tries with respect to neighbour and range searches, while the
external path length is significantly decreased. It also has the advantage of being easy to implement.
Our analysis shows that the expected depth of a stored element is O(log*n) for uniformly distributed
data.
Full paper (postscript)
Full paper (pdf)