TY - JOUR

T1 - Smoothed heights of tries and patricia tries

AU - Tong, Weitian

AU - Goebel, Randy

AU - Lin, Guohui

N1 - Publisher Copyright:
© 2015 Elsevier B.V.

PY - 2016/1/4

Y1 - 2016/1/4

N2 - Tries and patricia tries are two popular data structures for storing strings. Let Hn denote the height of the trie (the patricia trie, respectively) on a set of n strings. Under the uniform distribution model on the strings, it is well known that Hn/logn → 2 for tries and Hn/logn → 1 for patricia tries, when n approaches infinity. Nevertheless, in the worst case, the height of a trie can be unbounded and the height of a patricia trie is in Θ(n). To better understand the practical performance of both tries and patricia tries, 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 the trie and the patricia trie are both in Θ(logn).

AB - Tries and patricia tries are two popular data structures for storing strings. Let Hn denote the height of the trie (the patricia trie, respectively) on a set of n strings. Under the uniform distribution model on the strings, it is well known that Hn/logn → 2 for tries and Hn/logn → 1 for patricia tries, when n approaches infinity. Nevertheless, in the worst case, the height of a trie can be unbounded and the height of a patricia trie is in Θ(n). To better understand the practical performance of both tries and patricia tries, 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 the trie and the patricia trie are both in Θ(logn).

KW - Data structure

KW - Patricia trie

KW - Smoothed analysis

KW - Trie

UR - http://www.scopus.com/inward/record.url?scp=84948845063&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.02.009

DO - 10.1016/j.tcs.2015.02.009

M3 - Article

AN - SCOPUS:84948845063

SN - 0304-3975

VL - 609

SP - 620

EP - 626

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -