Partial match queries in random quadtrees

MaRDI QIDQ5743457zbMATH OpenFDO

Authors Nicolas Broutin, Ralph Neininger, Henning Sulzbach

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1107.2231, https://dl.acm.org/citation.cfm?id=2095199

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

Abstract: We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees 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 an independent and uniformly on $[0,1]$ random query $xi$ satisfies $$, where $kappa$ and $$ are explicit constants. We develop an approach based on the analysis of the cost $C_n(x)$ of any fixed query $xin[0,1]$, and give precise estimates for the variance and limit distribution of the cost $C_n(x)$. Our results permit to describe a limit process for the costs $C_n(x)$ as $x$ varies in $[0,1]$; one of the consequences is that $$.

Recommendations

• A limit process for partial match queries in random quadtrees and 2-d trees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Partial Match Queries in Random Quadtrees
• Fixed partial match queries in quadtrees
• Limit laws for partial match queries in quadtrees

Cites work

• 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 theorem for “quicksort”
• A limit theorem for recursively defined processes in Lp
• Analytic combinatorics
• Analytic variations on quadtrees
• Finite element mesh generation methods: A review and classification
• 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 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1545682 (Why is no real title available?)
• scientific article; zbMATH DE number 6876073 (Why is no real title available?)
• Hypergeometrics and the cost structure of quadtrees
• 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 relaxed multidimensional search trees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Partial match retrieval of multidimensional data
• Partial-Match Retrieval Algorithms
• Probability metrics and recursive algorithms
• Quad trees: A data structure for retrieval by composite keys
• Rank selection in multidimensional data

Cited in

(17)

• Analytic variations on quadtrees
• Expected worst-case partial match in random quadtries
• Limit laws for partial match queries in quadtrees
• A limit field for orthogonal range searches in two-dimensional random point search trees
• On the average performance of fixed partial match queries in random relaxed K-d trees
• Random partial match in quad-K-d trees
• Strong convergence of partial match queries in random quadtrees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• scientific article; zbMATH DE number 4014072 (Why is no real title available?)
• 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
• Partial Match Queries in Random Quadtrees
• Fixed partial match queries in quadtrees
• A probabilistic model for interfaces in a martensitic phase transition
• Partial match queries in relaxed \(K\)-\(\mathrm{d}t\) trees
• Partial Match Queries in Random k-d Trees
• A spatially-dependent fragmentation process

This page was built for publication: Partial match queries in random quadtrees

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