Laws of large numbers and tail inequalities for random tries and PATRICIA trees
type: Item
instance of: scholarly article
title: Laws of large numbers and tail inequalities for random tries and PATRICIA trees
zbMATH Open document ID: 1005.60032
DOI: 10.1016/S0377-0427(01)00458-7
published in: Journal of Computational and Applied Mathematics
publication date: 2002-08-22T00:00:00Z
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 1787594
zbMATH Keywords: trie
zbMATH Keywords: PATRICIA tree
zbMATH Keywords: probabilistic analysis
zbMATH Keywords: law of large numbers
zbMATH Keywords: concentration inequality
zbMATH Keywords: height of a tree
author: Luc Devroye
describes a project that uses: PATRICIA
MaRDI profile type: Publication
cites work: Weighted sums of certain dependent random variables
cites work: A sharp concentration inequality with applications
cites work: Dynamical sources in information theory: A general analysis of trie structures
cites work: A probabilistic analysis of the height of tries and of the complexity of triesort
cites work: The expected length of the longest probe sequence for bucket searching when the distribution is not uniform
cites work: A note on the probabilistic analysis of patricia trees
cites work: A study of trie-like structures under the density model
cites work: On the performance evaluation of extendible hashing and trie searching
cites work: Digital Search Trees Revisited
cites work: Q3940858
cites work: Expected Length of the Longest Probe Sequence in Hash Code Searching
cites work: Q3742733
cites work: Q3730026
cites work: Q5585020
cites work: On Talagrand's deviation inequalities for product measures
cites work: Q3124805
cites work: Q3496342
cites work: Q4226453
cites work: Analysis of Extendible Hashing
cites work: Asymptotical growth of a class of random trees
cites work: Paths in a random digital tree: limiting distributions
cites work: How many random questions are necessary to identify \(n\) distinct objects?
cites work: On the average height of trees in digital search and dynamic hashing
cites work: Some results on V-ary asymmetric tries
cites work: Q4028887
cites work: Patricia tries again revisited
cites work: On the height of digital trees and related problems
cites work: Q4508387
cites work: An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
cites work: Isoperimetry and integrability of the sum of independent Banach-space valued random variables
cites work: Sample boundedness of stochastic processes under increment conditions
cites work: A new isoperimetric inequality for product measure and the tails of sums of independent random variables
cites work: Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
cites work: New Gaussian estimates for enlarged balls
cites work: Sharper bounds for Gaussian and empirical processes
cites work: Concentration of measure and isoperimetric inequalities in product spaces
cites work: New concentration inequalities in product spaces
cites work: A new look at independence
description: scientific article; zbMATH DE number 1787594