Expected worst-case partial match in random quadtries

DOI10.1016/S0166-218X(03)00365-2zbMath1081.68009MaRDI QIDQ1827855

Luc P. Devroye, Zamora-Cura, Carlos

Publication date: 6 August 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Probabilistic analysisPartial matchMultivariate trie

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic analysis of the height of tries and of the complexity of triesort
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• On the average height of trees in digital search and dynamic hashing
• A study of trie-like structures under the density model
• Heuristics for partial-match retrieval data base design
• A new look at independence
• On Talagrand's deviation inequalities for product measures
• Paths in a random digital tree: limiting distributions
• Some results on V-ary asymmetric tries
• Analysis of Extendible Hashing
• MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES
• A sharp concentration inequality with applications
• The variance of a partial match retrieval in a multidimensional symmetric trie
• Partial match retrieval of multidimensional data
• Probability Inequalities for Sums of Bounded Random Variables
• New concentration inequalities in product spaces