TY - GEN
T1 - On the smoothed heights of trie and patricia index trees
AU - Tong, Weitian
AU - Goebel, Randy
AU - Lin, Guohui
PY - 2014
Y1 - 2014
N2 - Two of the most popular data structures for storing strings are the Trie and the Patricia index trees. Let Hn denote the height of the Trie (the Patricia, respectively) on a set of n strings. It is well known that under the uniform distribution model on the strings, for Trie Hn/ logn→2 and for Patricia Hn/logn→1, when n approaches infinity. Nevertheless, in the worst case, the height of the Trie on n strings is unbounded, and the height of the Patricia on n strings is in Θ(n). To better understand the practical performance of both the Trie and Patricia index trees, we investigate these two classical data structures in a smoothed analysis model. Given a set S = {s1, s2,.., sn} of n binary strings, we perturb the set by adding an i.i.d Bernoulli random noise to each bit of every string. We show that the resulting smoothed heights of Trie and Patricia trees are both Θ(logn).
AB - Two of the most popular data structures for storing strings are the Trie and the Patricia index trees. Let Hn denote the height of the Trie (the Patricia, respectively) on a set of n strings. It is well known that under the uniform distribution model on the strings, for Trie Hn/ logn→2 and for Patricia Hn/logn→1, when n approaches infinity. Nevertheless, in the worst case, the height of the Trie on n strings is unbounded, and the height of the Patricia on n strings is in Θ(n). To better understand the practical performance of both the Trie and Patricia index trees, we investigate these two classical data structures in a smoothed analysis model. Given a set S = {s1, s2,.., sn} of n binary strings, we perturb the set by adding an i.i.d Bernoulli random noise to each bit of every string. We show that the resulting smoothed heights of Trie and Patricia trees are both Θ(logn).
UR - http://www.scopus.com/inward/record.url?scp=84904766811&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-08783-2_9
DO - 10.1007/978-3-319-08783-2_9
M3 - Conference article
AN - SCOPUS:84904766811
SN - 9783319087825
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 94
EP - 103
BT - Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PB - Springer Verlag
T2 - 20th International Computing and Combinatorics Conference, COCOON 2014
Y2 - 4 August 2014 through 6 August 2014
ER -