Multiple choice tries and distributed hash tables
Luc Devroye, Gábor Lugosi, Gahyun Park, Wojciech Szpankowski · 2007
Tries were introduced in 1960 by Fredkin as an efficient method for searching and sorting digital data. Recent years have seen a resurgence of interest in tries that find applications in dynamic hashing, conflict resolution algorithms, leader election algorithms, IP addresses lookup, Lempel-Ziv compression schemes, and distributed hash tables. In some of these applications, most notably in distributed hash tables one needs to design a well balanced trie, that is, a trie with the height as close as possible to its fillup level. In this paper we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. Three cases are considered: k = 2, k is large but fixed, and k ∼ c logn. The goal in each case is to obtain tries as balanced as possible. Various parameters such as height and fill-up level are analyzed. It is shown that for two-choice tries a 50 % reduction in height is achieved when compared to ordinary tries. In a greedy on-line construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25%. In order to further reduce the height by another 25%, we design a more refined on-line algorithm. The total