Benutzer: Gast  Login
Titel:

Smoothed Analysis of Trie Height

Dokumenttyp:
Technical Report
Autor(en):
Stefan Eckhardt; Sven Kosub; Johannes Nowak
Abstract:
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...     »
Stichworte:
Trie Height; Smoothed Analysis; Edit Perturbations; Probabilistic Finite Automatons
Jahr:
2007
Jahr / Monat:
2007-07-01 00:00:00
Seiten/Umfang:
28
 BibTeX