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

DOI10.1016/j.spa.2018.08.014zbMath1422.60020arXiv1711.11354OpenAlexW2962799130MaRDI QIDQ2274287

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

quadtree convergence in distribution analysis of algorithms contraction method range query random partition partial match

Mathematics Subject Classification ID

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

Cites Work

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

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