An analytic approach to the asymptotic variance of trie statistics and related structures

DOI10.1016/J.TCS.2014.01.024zbMATH Open1337.68081arXiv1303.4244OpenAlexW2070095503MaRDI QIDQ2437771FDOQ2437771

Authors: Michael Fuchs, Hsien-Kuei Hwang, Vytas Zacharovas 

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We develop analytic tools for the asymptotics of general trie statistics, which are particularly advantageous for clarifying the asymptotic variance. Many concrete examples are discussed for which new Fourier expansions are given. The tools are also useful for other splitting processes with an underlying binomial distribution. We specially highlight Philippe Flajolet's contribution in the analysis of these random structures.

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

Recommendations

• New results on the size of tries
• On The variance of the extremal path length in a symmetric digital trie
• The variance of the number of 2-protected nodes in a trie
• Profiles of Tries
• scientific article; zbMATH DE number 3978406

zbMATH Keywords

Mellin transformvariancedigital treesbinomial splitting processcontention resolution algorithmsperiodic fluctuations

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Title not available (Why is that?)
• Analytic combinatorics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mellin transforms and asymptotics: Harmonic sums
• A general limit theorem for recursive algorithms and combinatorial structures
• Motif statistics.
• Minimal clade size and external branch length under the neutral coalescent
• Title not available (Why is that?)
• Asymptotics of the moments of extreme-value related distribution functions
• A Generalisation of Stirling's Formula.
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Phase transition in a generalized Eden growth model on a tree
• Special issue: Average-case analysis of algorithms
• On the distribution for the duration of a randomized leader election algorithm
• Analysis of an asymmetric leader election algorithm
• Dynamical sources in information theory: A general analysis of trie structures
• Data Movement in Odd-Even Merging
• Title not available (Why is that?)
• How to select a loser
• Title not available (Why is that?)
• Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model
• Approximate counting: a detailed analysis
• Periodic oscillations in the analysis of algorithms and their cancellations
• Asymptotic variance of random symmetric digital search trees
• Title not available (Why is that?)
• Partial match retrieval of multidimensional data
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• Radix Exchange—An Internal Sorting Method for Digital Computers
• Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
• Probabilistic counting algorithms for data base applications
• Title not available (Why is that?)
• On Buffon Machines and Numbers
• Title not available (Why is that?)
• Analytical depoissonization and its applications
• Title not available (Why is that?)
• Profiles of Tries
• A multivariate view of random bucket digital search trees
• On the variance of a class of inductive valuations of data structures for digital search
• Analytic variations on bucket selection and sorting
• Order statistics for the Cantor-Fibonacci distribution
• The complexity of generating an exponentially distributed variate
• Title not available (Why is that?)
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• The average number of registers needed to evaluate a binary tree optimally
• An improved algorithm for transitive closure on acyclic digraphs
• On The variance of the extremal path length in a symmetric digital trie
• Analytic properties of multiple-access trees
• <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
• Analysis of contention tree algorithms
• On tries, contention trees and their analysis
• Analysis of a stack algorithm for random multiple-access communication
• On the balance property of Patricia tries: External path length viewpoint
• Recurrence relations based on minimization
• On some applications of formulae of Ramanujan in the analysis of algorithms
• MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES
• New results on the size of tries
• On the performance evaluation of extendible hashing and trie searching
• Words with a generalized restricted growth property
• Title not available (Why is that?)
• The asymptotic behavior of a family of sequences
• Renewal theory in the analysis of tries and strings
• On the shape of the fringe of various types of random trees
• Asymptotic analysis of the moments of the Cantor distribution
• The significance of Jacob Bernoulli's \textit{Ars Conjectandi} for the philosophy of probability today
• On the expectation of the maximum of IID geometric random variables
• Analysis of Extendible Hashing
• Reducing conflict resolution time for solving graph problems in broadcast communications
• Random list permutations in place
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sorting algorithms for broadcast communications: mathematical analysis.
• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• Universal asymptotics for random tries and PATRICIA trees
• Title not available (Why is that?)
• The Subtree Size Profile of Plane-oriented Recursive Trees
• On the stack-size of general tries
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees

Cited In (13)

• A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
• Title not available (Why is that?)
• Node profiles of symmetric digital search trees: Concentration properties
• A study of trie-like structures under the density model
• On 2-protected nodes in random digital trees
• A binomial splitting process in connection with corner parking problems
• Central limit theorems for additive functionals and fringe trees in tries
• Dependence between path-length and size in random digital trees
• From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader
• On the variety of shapes in digital trees
• The Wiener index of random digital trees
• New results on the size of tries
• Asymptotic normality for the size of graph tries built from M-ary tree labelings

Uses Software

• HyperLogLog
• PATRICIA

This page was built for publication: An analytic approach to the asymptotic variance of trie statistics and related structures

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