Premium
Multiple choice tries and distributed hash tables
Author(s) -
Devroye Luc,
Lugosi Gábor,
Park Gahyun,
Szpankowski Wojciech
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20234
Subject(s) - string (physics) , mathematics , constant (computer programming) , hash function , combinatorics , bounded function , perfect hash function , binary logarithm , hash table , reduction (mathematics) , discrete mathematics , trie , simple (philosophy) , computation , randomized algorithm , online algorithm , asymptotically optimal algorithm , data structure , computer science , algorithm , mathematical analysis , geometry , computer security , philosophy , epistemology , mathematical physics , programming language
In this article 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 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 ≥ 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). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009