# zbMATH — the first resource for mathematics

Multiple choice tries and distributed hash tables. (English) Zbl 1172.68067
Summary: 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\sim c\log n$$. 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 with ordinary tries. In a greedy online construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25%. To further reduce the height by another 25%, we design a more refined online algorithm. The total computation time of the algorithm is $$O(n\log n)$$. Furthermore, when we choose the best among $$k\geq 2$$ strings, then for large but fixed $$k$$ the height is asymptotically equal to the typical depth in a trie.
Finally, we show that further improvement can be achieved if the number of choices for each string is proportional to $$\log n$$. In this case highly balanced trees can be constructed by a simple greedy algorithm for which the difference between the height and the fill-up level is bounded by a constant with high probability. This, in turn, has implications for distributed hash tables, leading to a randomized ID management algorithm in peer-to-peer networks such that, with high probability, the ratio between the maximum and the minimum load of a processor is $$O(1)$$.
##### MSC:
 68W40 Analysis of algorithms 68P05 Data structures
PATRICIA
Full Text: