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 (9)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Laws of large numbers and tail inequalities for random tries and PATRICIA trees
