A limit process for partial match queries in random quadtrees and 2-d trees

DOI10.1214/12-AAP912MaRDI QIDQ389077zbMATH OpenFDO

Authors Nicolas Broutin, Ralph Neininger, Henning Sulzbach

Publication date 17 January 2014

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

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

zbMATH Keywords

limit distributionquadtreeanalysis of algorithmscontraction method

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40) Data structures (68P05) Functional limit theorems; invariance principles (60F17) Combinatorial probability (60C05)

Abstract: We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quadtrees and $k$-d trees). We assume the traditional model where the data consist of independent and uniform points in the unit square. For this model, in a structure on $n$ points, it is known that the number of nodes $C_n(xi)$ to visit in order to report the items matching a random query $xi$, independent and uniformly distributed on $[0,1]$, satisfies $$, where $kappa$ and $$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(s)$ of any fixed query $sin[0,1]$, and give precise estimates for the variance and limit distribution of the cost $C_n(x)$. Our results permit us to describe a limit process for the costs $C_n(x)$ as $x$ varies in $[0,1]$; one of the consequences is that $$; this settles a question of Devroye [Pers. Comm., 2000].

Recommendations

• Partial match queries in random quadtrees
• Limit laws for partial match queries in quadtrees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Fixed partial match queries in quadtrees
• Partial Match Queries in Random Quadtrees

Cites work

• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1545682 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A fixed point theorem for distributions
• A functional limit theorem for the profile of search trees
• 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 recursively defined processes in Lp
• A limit theorem for “quicksort”
• A structured computer system model
• An Analysis of Randomd-Dimensional Quad Trees
• Analytic combinatorics
• Analytic variations on quadtrees
• Branching processes in the analysis of the heights of trees
• Finite element mesh generation methods: A review and classification
• Foundations of multidimensional and metric data structures.
• Hypergeometrics and the cost structure of quadtrees
• Ignoring ignorance and agreeing to disagree
• Limit laws for partial match queries in quadtrees
• Multidimensional binary search trees used for associative searching
• On a functional contraction method
• On a multivariate contraction method for random recursive structures with applications to quicksort
• On the analysis of stochastic divide and conquer algorithms
• On the average performance of orthogonal range search in multidimensional data structures
• On the contraction method with degenerate limit equation.
• On the silhouette of binary search trees
• Partial Match Queries in Random Quadtrees
• Partial Match Queries in Random k-d Trees
• Partial match queries in relaxed multidimensional search trees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Partial-Match Retrieval Algorithms
• Probability Inequalities for Sums of Bounded Random Variables
• Probability metrics and recursive algorithms
• Quad trees: A data structure for retrieval by composite keys
• Rank selection in multidimensional data

Cited in

(16)

• On the expected cost of partial match queries in random quad-\(K\)-d trees
• The dual tree of a recursive triangulation of the disk
• Fixed partial match queries in quadtrees
• Partial match queries in random quadtrees
• Limit laws for partial match queries in quadtrees
• Strong convergence of partial match queries in random quadtrees
• On the cost of fixed partial match queries in K-d trees
• scientific article; zbMATH DE number 1545682 (Why is no real title available?)
• A limit process for partial match queries in random quadtrees and 2-d trees
• On a functional contraction method
• A limit field for orthogonal range searches in two-dimensional random point search trees
• Around the root of random multidimensional quadtrees
• Partial Match Queries in Random Quadtrees
• Expected worst-case partial match in random quadtries
• Process convergence for the complexity of radix selection on Markov sources
• Partial match queries in two-dimensional quadtrees: a probabilistic approach

This page was built for publication: A limit process for partial match queries in random quadtrees and 2-d trees

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