Laws of large numbers and tail inequalities for random tries and PATRICIA trees
From MaRDI portal
Publication:1612291
DOI10.1016/S0377-0427(01)00458-7zbMath1005.60032MaRDI QIDQ1612291
Publication date: 22 August 2002
Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)
Geometric probability and stochastic geometry (60D05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
An Analysis of the Height of Tries with Random Weights on the Edges, Profiles of PATRICIA tries, The degree profile of random Pólya trees, Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els, Local tail bounds for functions of independent random variables, Moment inequalities for functions of independent random variables, Profile of Tries, Asymmetric Rényi Problem, Multiple choice tries and distributed hash tables
Uses Software
Cites Work
- Isoperimetry and integrability of the sum of independent Banach-space valued random variables
- A probabilistic analysis of the height of tries and of the complexity of triesort
- Sample boundedness of stochastic processes under increment conditions
- On the height of digital trees and related problems
- On the performance evaluation of extendible hashing and trie searching
- Asymptotical growth of a class of random trees
- On the average height of trees in digital search and dynamic hashing
- A new isoperimetric inequality for product measure and the tails of sums of independent random variables
- A study of trie-like structures under the density model
- Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
- New Gaussian estimates for enlarged balls
- Sharper bounds for Gaussian and empirical processes
- How many random questions are necessary to identify \(n\) distinct objects?
- Dynamical sources in information theory: A general analysis of trie structures
- Concentration of measure and isoperimetric inequalities in product spaces
- A new look at independence
- Weighted sums of certain dependent random variables
- An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
- On Talagrand's deviation inequalities for product measures
- Patricia tries again revisited
- The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
- Paths in a random digital tree: limiting distributions
- Digital Search Trees Revisited
- Some results on V-ary asymmetric tries
- Expected Length of the Longest Probe Sequence in Hash Code Searching
- Analysis of Extendible Hashing
- A note on the probabilistic analysis of patricia trees
- A sharp concentration inequality with applications
- New concentration inequalities in product spaces
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
