Profiles of Tries

DOI10.1137/070685531MaRDI QIDQ3642866zbMATH OpenOpenAlexFDO

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

Publication date 6 November 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/a7a533d798d298ad147067aa82968ebad93d923b

zbMATH Keywords

analytic poissonizationdepthdigital treesfill-up levelheightMellin transformprofilesaddle-point methodshortest pathsingularity analysistries

Mathematics Subject Classification ID

Trees (05C05) Central limit and other weak theorems (60F05) Searching and sorting (68P10) Analysis of algorithms (68W40)

Recommendations

• Profile of Tries
• Profiles of PATRICIA tries
• Expected external profile of PATRICIA tries
• The profile of relations
• Signifikanztest für Kopfschadenprofile
• Publication:3035296
• Protected node profile of tries
• scientific article; zbMATH DE number 4186919
• On Profile Likelihood

Cited in

(42)

• A note on the asymptotic behavior of the depth of tries
• Profiles of PATRICIA tries
• Limit theorems for patterns in phylogenetic trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Asymptotic expectation of protected node profile in random digital search trees
• scientific article; zbMATH DE number 1696631 (Why is no real title available?)
• Trie structure for graph sequences
• Limit theorems for subtree size profiles of increasing trees
• A new binomial recurrence arising in a graphical compression algorithm
• Towards a complete characterization of tries
• A Uniform Approach to the Analysis of Trie Structures That Store Prefixing-Keys
• On the number of full levels in tries
• An Analysis of the Height of Tries with Random Weights on the Edges
• Average-Case Analysis of Cousins in m-ary Tries
• The height of list-tries and TST
• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 4007734 (Why is no real title available?)
• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• The degree profile of random Pólya trees
• Protected node profile of tries
• On a recurrence arising in graph compression
• Dependence between external path-length and size in random tries
• New results on the size of tries
• Trie size in a dynamic list structure
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• Expected external profile of PATRICIA tries
• Asymmetric Rényi problem
• The Wiener index of random digital trees
• Gaussian distribution of trie depth for strongly tame sources
• Shape measures of random increasing k-trees
• ON CLIMBING TRIES
• Profile of Tries
• Average profiles, from tries to suffix-trees
• The expected profile of digital search trees
• The oscillatory distribution of distances in random tries
• Towards more realistic probabilistic models for data structures: the external path length in tries under the Markov model
• Node profiles of symmetric digital search trees: Concentration properties
• On tries, contention trees and their analysis
• A probabilistic analysis of the height of tries and of the complexity of triesort
• Renewal theory in the analysis of tries and strings
• Smoothed heights of tries and patricia tries
• A functional limit theorem for the profile of \(b\)-ary trees

This page was built for publication: Profiles of Tries

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