An analytic approach to the asymptotic variance of trie statistics and related structures
From MaRDI portal
Publication:2437771
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4162250 (Why is no real title available?)
- scientific article; zbMATH DE number 5763313 (Why is no real title available?)
- scientific article; zbMATH DE number 3932385 (Why is no real title available?)
- scientific article; zbMATH DE number 3978406 (Why is no real title available?)
- scientific article; zbMATH DE number 4051016 (Why is no real title available?)
- scientific article; zbMATH DE number 3757718 (Why is no real title available?)
- scientific article; zbMATH DE number 3788009 (Why is no real title available?)
- scientific article; zbMATH DE number 53861 (Why is no real title available?)
- scientific article; zbMATH DE number 3593676 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 1545683 (Why is no real title available?)
- scientific article; zbMATH DE number 1377041 (Why is no real title available?)
- scientific article; zbMATH DE number 850224 (Why is no real title available?)
- scientific article; zbMATH DE number 3390782 (Why is no real title available?)
- scientific article; zbMATH DE number 3040053 (Why is no real title available?)
- <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
- A Generalisation of Stirling's Formula.
- A general limit theorem for recursive algorithms and combinatorial structures
- A master theorem for discrete divide and conquer recurrences
- A multivariate view of random bucket digital search trees
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
- An improved algorithm for transitive closure on acyclic digraphs
- Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model
- Analysis of Extendible Hashing
- Analysis of a stack algorithm for random multiple-access communication
- Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
- Analysis of an asymmetric leader election algorithm
- Analysis of contention tree algorithms
- Analytic combinatorics
- Analytic properties of multiple-access trees
- Analytic variations on bucket selection and sorting
- Analytical depoissonization and its applications
- Approximate counting: a detailed analysis
- Asymptotic analysis of the moments of the Cantor distribution
- Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
- Asymptotic variance of random symmetric digital search trees
- Asymptotics of the moments of extreme-value related distribution functions
- Data Movement in Odd-Even Merging
- Digital trees and memoryless sources: from arithmetics to analysis
- Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees
- Dynamical sources in information theory: A general analysis of trie structures
- How to select a loser
- Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
- MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES
- Mellin transforms and asymptotics: Finite differences and Rice's integrals
- Mellin transforms and asymptotics: Harmonic sums
- Minimal clade size and external branch length under the neutral coalescent
- Motif statistics.
- New results on the size of tries
- On Buffon machines and numbers
- On The variance of the extremal path length in a symmetric digital trie
- On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
- On some applications of formulae of Ramanujan in the analysis of algorithms
- On the balance property of Patricia tries: External path length viewpoint
- On the distribution for the duration of a randomized leader election algorithm
- On the expectation of the maximum of IID geometric random variables
- On the performance evaluation of extendible hashing and trie searching
- On the shape of the fringe of various types of random trees
- On the stack-size of general tries
- On the variance of a class of inductive valuations of data structures for digital search
- On tries, contention trees and their analysis
- On unary nodes in tries
- Order statistics for the Cantor-Fibonacci distribution
- Partial match retrieval of multidimensional data
- Periodic oscillations in the analysis of algorithms and their cancellations
- Phase transition in a generalized Eden growth model on a tree
- Probabilistic counting algorithms for data base applications
- Profiles of Tries
- Radix Exchange—An Internal Sorting Method for Digital Computers
- Random list permutations in place
- Recurrence relations based on minimization
- Reducing conflict resolution time for solving graph problems in broadcast communications
- Renewal theory in the analysis of tries and strings
- Sorting algorithms for broadcast communications: mathematical analysis.
- Special issue: Average-case analysis of algorithms
- The asymptotic behavior of a family of sequences
- The average number of registers needed to evaluate a binary tree optimally
- The complexity of generating an exponentially distributed variate
- The significance of Jacob Bernoulli's \textit{Ars Conjectandi} for the philosophy of probability today
- The subtree size profile of plane-oriented recursive trees
- The variance for partial match retrievals in \(k\)-dimensional bucket digital trees
- Universal asymptotics for random tries and PATRICIA trees
- Words with a generalized restricted growth property
Cited in
(13)- scientific article; zbMATH DE number 3896283 (Why is no real title available?)
- A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
- A binomial splitting process in connection with corner parking problems
- New results on the size of 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
- Central limit theorems for additive functionals and fringe trees in tries
- A study of trie-like structures under the density model
- Asymptotic normality for the size of graph tries built from M-ary tree labelings
- On 2-protected nodes in random digital trees
- Node profiles of symmetric digital search trees: Concentration properties
- The Wiener index of random digital trees
- On the variety of shapes in digital trees
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)
