Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model

Kevin Leckey; Ralph Neininger; Wojciech Szpankowski

doi:10.1137/1.9781611973105.63

Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model

Abstrakt

Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used in diverse contexts ranging from document taxonomy to IP addresses lookup, from data compression (i.e., Lempel- Ziv'77 scheme) to dynamic hashing, from partial-match queries to speech recognition, from leader election algorithms to distributed hashing tables and graph compression. While the performance of tries under a realistic probabilistic model is of signicant importance, its analysis, even for simplest memoryless sources, has proved dicult. Rigorous ndings about inherently complex parameters were rarely analyzed (with a few notable exceptions) under more realistic models of string generations. In this paper we meet these challenges: By a novel use of the contraction method combined with analytic techniques we prove a central limit theorem for the external path length of a trie under a general Markov source. In particular, our results apply to the Lempel-Ziv'77 code. We envision that the methods described here will have further applications to other trie parameters and data structures

Cytowania

3

CrossRef
0

Web of Science
5

Scopus

Autorzy (3)

Kevin Leckey
- .. ...
Ralph Neininger
- .. ..
Wojciech Szpankowski prof. dr inż.
- Purdue University .

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Aktywność konferencyjna
Typ:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:: Proceedings , ACM-SIAM Symposium on Discrete Algorithms SODA 2013 strony 877 - 886
Język:: angielski
Rok wydania:: 2013
Opis bibliograficzny:: Leckey K., Neininger R., Szpankowski W.: Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model// Proceedings , ACM-SIAM Symposium on Discrete Algorithms SODA 2013/ New Orleans: Society for Industrial and Aplied Mathematics, 2013, s.877-886
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1137/1.9781611973105.63
Weryfikacja:: Politechnika Gdańska