Towards more realistic probabilistic models for data structures: The external path length in tries under the Markov model

Kevin Leckey, Ralph Neininger, Wojciech Szpankowski

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

4 Citations (Scopus)

Abstract

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 significant importance, its analysis, even for simplest memoryless sources, has proved difficult. Rigorous findings 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.

Original languageEnglish
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherSociety for Industrial & Applied Mathematics (SIAM)
Pages877-886
Number of pages10
ISBN (Print)9781611972511
Publication statusPublished - 2013
Externally publishedYes
EventACM/SIAM Symposium on Discrete Algorithms 2013 - Astor Crown Plaza Hotel, New Orleans, United States of America
Duration: 6 Jan 20138 Jan 2013
Conference number: 24th
http://www.siam.org/meetings/da13/

Conference

ConferenceACM/SIAM Symposium on Discrete Algorithms 2013
Abbreviated titleSODA 2013
CountryUnited States of America
CityNew Orleans
Period6/01/138/01/13
Internet address

Cite this