Limit laws for partial match queries in quadtrees

DOI10.1214/aoap/1015345300zbMath1012.68058OpenAlexW2049990738MaRDI QIDQ1872463

Ralph Neininger, Ludger Rüschendorf

Publication date: 6 May 2003

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1015345300

zbMATH Keywords

contraction methodpartial match query

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Searching and sorting (68P10)

Related Items

A limit process for partial match queries in random quadtrees and 2-d trees, Partial match queries in random quadtrees, Psi-series method for equality of random trees and quadratic convolution recurrences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some asymptotic theory for the bootstrap
• A fixed point theorem for distributions
• Analytic variations on quadtrees
• Quad trees: A data structure for retrieval by composite keys
• The contraction method for recursive algorithms
• Partial match queries in relaxed multidimensional search trees
• On the analysis of stochastic divide and conquer algorithms
• Some properties of a limiting distribution in Quicksort
• On the internal path length ofd-dimensional quad trees
• Total Path Length for Random Recursive Trees
• Probability metrics and recursive algorithms
• Analysis of quickselect : an algorithm for order statistics
• A limit theorem for “quicksort”