Profile of Tries

DOI10.1007/978-3-540-78773-0_1MaRDI QIDQ5458512zbMATHOpenAlexFDO

Authors Gahyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_1

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Profiles of Tries
• Towards a complete characterization of tries
• Average profiles, from tries to suffix-trees
• Towards more realistic probabilistic models for data structures: the external path length in tries under the Markov model
• Concentration of Size and Path Length of Tries

Cites work

• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Analytical depoissonization and its applications
• Asymptotic normality of recursive algorithms via martingale difference arrays
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Average profiles, from tries to suffix-trees
• How to select a loser
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• Mellin transforms and asymptotics: Harmonic sums
• On the number of full levels in tries
• Paths in a random digital tree: limiting distributions
• Profile of Tries
• Profiles of random trees: plane-oriented recursive trees
• Towards a complete characterization of tries

Cited in

(16)

• Protected node profile of tries
• Maximum likelihood analysis of algorithms and data structures
• The average profile of suffix trees
• Renewal theory in the analysis of tries and strings
• Average profiles, from tries to suffix-trees
• Profile of Tries
• A generalization of the trie data structure
• Trie structure for graph sequences
• Towards a complete characterization of tries
• Statistical Properties of Factor Oracles
• Gaussian distribution of trie depth for strongly tame sources
• Profiles of Tries
• A functional limit theorem for the profile of \(b\)-ary trees
• Statistical properties of factor oracles
• Average-case analysis of approximate trie search
• Towards more realistic probabilistic models for data structures: the external path length in tries under the Markov model

This page was built for publication: Profile of Tries

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