Smoothed Analysis of Trie Height

Tries are very simple general purpose data structures for information retrieval. A crucial parameter of a trie is its height. In the worst case the height is unbounded when the trie is built over a set of n strings. Analytical investigations have shown that the average height under many random sources is logarithmic in n. Experimental studies of trie height suggest that this holds for non-random data. In order to give an analytical explanation to these findings we perform a smoothed analysis of trie height.\\ \\ Smoothed analysis combines elements from both, worst-case and average-case analysis: the paradigm assumes that inputs are chosen by an adversary and that the costs are expected costs over slight random pertubations of the chosen inputs. We consider a special class of string perturbation functions which can be modelled by probabilistic finite automata (PFAs). Those perturbation functions constitute an extension of a very natural class of random edit perturbations. We observe that for the case of random deletions the smoothed trie height is unbounded.\\ We introduce read-deterministic star-like perturbation functions, which include random substitutions and insertion as a special case, and give a necessary and sufficient condition for the smoothed trie height under read-deterministic star-like perturbation functions being logarithmic. This condition is particularly appealing since it can easily be checked by looking at the transition probabilities of the corresponding probabilistic automaton.     «

Tries are very simple general purpose data structures for information retrieval. A crucial parameter of a trie is its height. In the worst case the height is unbounded when the trie is built over a set of n strings. Analytical investigations have shown that the average height under many random sources is logarithmic in n. Experimental studies of trie height suggest that this holds for non-random data. In order to give an analytical explanation to these findings we perform a smoothed analysis of...     »