A limit field for orthogonal range searches in two-dimensional random point search trees

DOI10.1016/J.SPA.2018.08.014MaRDI QIDQ2274287zbMATH OpenOpenAlexFDO

Authors Nicolas Broutin, Henning Sulzbach

Publication date 19 September 2019

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.11354

zbMATH Keywords

analysis of algorithmscontraction methodconvergence in distributionpartial matchquadtreerandom partitionrange query

Mathematics Subject Classification ID

Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05) Functional limit theorems; invariance principles (60F17) Random fields (60G60) Information storage and retrieval of data (68P20)

Abstract: We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. We also state similar results for $2$-d trees. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an old question of Chanzy, Devroye and Zamora-Cura [emph{Acta Inf.}, 37:355--383, 2000]

Recommendations

• A limit process for partial match queries in random quadtrees and 2-d trees
• Limit laws for partial match queries in quadtrees
• Strong convergence of partial match queries in random quadtrees
• Partial match queries in random quadtrees
• Phase changes in random point quadtrees

Cites work

• A fixed point theorem for distributions
• A general limit theorem for recursive algorithms and combinatorial structures
• A limit process for partial match queries in random quadtrees and 2-d trees
• A limit theorem for “quicksort”
• An Analysis of Randomd-Dimensional Quad Trees
• Analysis of range search for random \(k-d\) trees
• Analytic variations on quadtrees
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Branching processes in the analysis of the heights of trees
• Contraction mappings and extensions
• Decomposable searching problems
• Foundations of multidimensional and metric data structures.
• scientific article; zbMATH DE number 193011 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• Hypergeometrics and the cost structure of quadtrees
• Multidimensional binary search trees used for associative searching
• On a functional contraction method
• On the average performance of orthogonal range search in multidimensional data structures
• On the Deviations of the Empiric Distribution Function of Vector Chance Variables
• Partial Match Queries in Random k-d Trees
• Partial match queries in random quadtrees
• Partial Match Queries in Random Quadtrees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Partial match retrieval of multidimensional data
• Probability metrics and recursive algorithms
• Quad trees: A data structure for retrieval by composite keys
• Squarish \(k\)-\(d\) trees
• Strong convergence of partial match queries in random quadtrees
• The contraction method for recursive algorithms
• The dual tree of a recursive triangulation of the disk
• Universal Limit Laws for Depths in Random Trees

Cited in

(1)

• Phase changes in random point quadtrees

This page was built for publication: A limit field for orthogonal range searches in two-dimensional random point search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274287)