On the variety of shapes in digital trees

DOI10.1007/s10959-016-0700-xzbMath1378.05025arXiv1607.00645OpenAlexW2963053522MaRDI QIDQ1692230

Mark Daniel Ward, Hosam M. Mahmoud, Jeffrey B. Gaither

Publication date: 26 January 2018

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

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

zbMATH Keywords

motifMellin transformfunctional equationrecurrenceanalysis of algorithmsrandom treescombinatorics on wordsdigital treessimilarity of stringspoissonizationdigital data

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Data structures (68P05) Information storage and retrieval of data (68P20)

Cites Work

• A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
• Mellin transforms and asymptotics: Harmonic sums
• On the variance of a class of inductive valuations of data structures for digital search
• Asymptotical growth of a class of random trees
• Analytical depoissonization and its applications
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Asymptotic joint normality of counts of uncorrelated motifs in recursive trees
• Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model
• On the Asymptotic Probability of Forbidden Motifs on the Fringe of Recursive Trees
• Average-Case Analysis of Cousins in m-ary Tries
• On the Variety of Shapes on the Fringe of a Random Recursive Tree
• Asymptotic variance of random symmetric digital search trees
• The Variance of the Number of 2-Protected Nodes in a Trie
• Transfer theorems and asymptotic distributional results for m‐ary search trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item