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

zbMATH Open1300.68021MaRDI QIDQ405180FDOQ405180

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

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

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

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)

Cites Work

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

Cited In (5)

• 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
• Asymptotic normality for the size of graph tries built from M-ary tree labelings

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)