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

DOI10.1214/12-AAP912zbMATH Open1358.68080arXiv1202.1342MaRDI QIDQ389077FDOQ389077

Authors: Nicolas Broutin, Ralph Neininger, Henning Sulzbach 

Publication date: 17 January 2014

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

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].

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

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

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)

Cites Work

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

Cited In (16)

• 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
• Title not available (Why is that?)
• On the cost of fixed partial match queries in \(K\)-d trees
• 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
• On the expected cost of partial match queries in random quad-\(K\)-d trees

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)