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

DOI10.1137/1.9781611973105.63zbMATH Open1422.68051arXiv1207.0302OpenAlexW2951629938MaRDI QIDQ5741771FDOQ5741771

Authors: Kevin Leckey, Ralph Neininger, Wojciech Szpankowski 

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1207.0302

Recommendations

• Towards a complete characterization of tries
• Concentration of Size and Path Length of Tries
• Profile of Tries
• Profiles of Tries
• Dynamical sources in information theory: A general analysis of trie structures

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (7)

• Profile of Tries
• Towards a complete characterization of tries
• On densities for solutions to stochastic fixed point equations
• The fixed points of the multivariate smoothing transform
• Size and path length of Patricia tries: Dynamical sources context
• Joint string complexity for Markov sources: small data matters
• Title not available (Why is that?)

This page was built for publication: Towards more realistic probabilistic models for data structures: the external path length in tries under the Markov model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741771)