A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries

MaRDI QIDQ405180zbMATH OpenFDO

Authors Michael Fuchs, Chung-Kuei Lee

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p69

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

momentsWiener indexdigital treesmultivariate limit lawsnodes of fixed out-degreetotal path length

Mathematics Subject Classification ID

Trees (05C05) Central limit and other weak theorems (60F05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• Limiting Distribution for the Depth in PATRICIA Tries
• Limit laws for the height in PATRICIA tries
• Central limit theorems for additive functionals and fringe trees in tries
• scientific article; zbMATH DE number 3978406
• Universal asymptotics for random tries and PATRICIA trees

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3265496 (Why is no real title available?)
• A Generalisation of Stirling's Formula.
• A general limit theorem for recursive algorithms and combinatorial structures
• A multivariate view of random bucket digital search trees
• A survey of multivariate aspects of the contraction method
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Analytic combinatorics
• Analytical depoissonization and its applications
• Asymptotic variance of random symmetric digital search trees
• Digital trees and memoryless sources: from arithmetics to analysis
• Dynamical sources in information theory: A general analysis of trie structures
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Mellin transforms and asymptotics: Harmonic sums
• On the number of 2-protected nodes in tries and suffix trees
• On the variance of a class of inductive valuations of data structures for digital search
• Profiles of Tries
• Size and path length of Patricia tries: Dynamical sources context
• The Wiener index of random digital trees
• The variance of the number of 2-protected nodes in a trie

Cited in

(5)

• Asymptotic normality for the size of graph tries built from M-ary tree labelings
• On 2-protected nodes in random digital trees
• Dependence between path-length and size in random digital trees
• On the variety of shapes in digital trees
• The Wiener index of random digital trees

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries

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