An analytic approach to the asymptotic variance of trie statistics and related structures
From MaRDI portal
Publication:2437771
DOI10.1016/j.tcs.2014.01.024zbMath1337.68081arXiv1303.4244MaRDI QIDQ2437771
Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.4244
Mellin transform; variance; digital trees; binomial splitting process; contention resolution algorithms; periodic fluctuations
68P05: Data structures
Related Items
From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader, Dependence between path-length and size in random digital trees, A binomial splitting process in connection with corner parking problems, The Wiener Index of Random Digital Trees, On 2-protected nodes in random digital trees, Node profiles of symmetric digital search trees: Concentration properties, Asymptotic normality for the size of graph tries built from M-ary tree labelings, A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries, On the variety of shapes in digital trees, Central limit theorems for additive functionals and fringe trees in tries
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On tries, contention trees and their analysis
- Mellin transforms and asymptotics: Harmonic sums
- Mellin transforms and asymptotics: Finite differences and Rice's integrals
- Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
- On the variance of a class of inductive valuations of data structures for digital search
- How to select a loser
- Words with a generalized restricted growth property
- The asymptotic behavior of a family of sequences
- Renewal theory in the analysis of tries and strings
- Phase transition in a generalized Eden growth model on a tree
- Asymptotics of the moments of extreme-value related distribution functions
- On the performance evaluation of extendible hashing and trie searching
- Approximate counting: a detailed analysis
- Probabilistic counting algorithms for data base applications
- An improved algorithm for transitive closure on acyclic digraphs
- On the balance property of Patricia tries: External path length viewpoint
- The significance of Jacob Bernoulli's \textit{Ars Conjectandi} for the philosophy of probability today
- Analytical depoissonization and its applications
- Reducing conflict resolution time for solving graph problems in broadcast communications
- Random list permutations in place
- Recurrence relations based on minimization
- The average number of registers needed to evaluate a binary tree optimally
- On The variance of the extremal path length in a symmetric digital trie
- On the distribution for the duration of a randomized leader election algorithm
- Analysis of an asymmetric leader election algorithm
- A general limit theorem for recursive algorithms and combinatorial structures
- Analytic variations on bucket selection and sorting
- Universal asymptotics for random tries and PATRICIA trees
- Special issue: Average-case analysis of algorithms
- Dynamical sources in information theory: A general analysis of trie structures
- Motif statistics.
- Sorting algorithms for broadcast communications: mathematical analysis.
- Asymptotic analysis of the moments of the Cantor distribution
- Order statistics for the Cantor-Fibonacci distribution
- Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
- On the expectation of the maximum of IID geometric random variables
- On the Stack-Size of General Tries
- On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
- A Generalisation of Stirling's Formula.
- Radix Exchange—An Internal Sorting Method for Digital Computers
- Asymptotic variance of random symmetric digital search trees
- On the shape of the fringe of various types of random trees
- Profiles of Tries
- Analysis of a stack algorithm for random multiple-access communication
- Analytic properties of multiple-access trees
- <tex>Q</tex>-ary collision resolution algorithms in random-access systems with free or blocked channel access
- The complexity of generating an exponentially distributed variate
- Analysis of Extendible Hashing
- On some applications of formulae of Ramanujan in the analysis of algorithms
- Data Movement in Odd-Even Merging
- MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES
- Analysis of contention tree algorithms
- New results on the size of tries
- A multivariate view of random bucket digital search trees
- Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model
- Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
- The Subtree Size Profile of Plane-oriented Recursive Trees
- Partial match retrieval of multidimensional data
- On Buffon Machines and Numbers
- Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
- Minimal clade size and external branch length under the neutral coalescent
- Distribution of the size of random hash trees, pebbled hash trees and \(N\)-trees
