Partial match queries in two-dimensional quadtrees: a probabilistic approach

DOI10.1239/AAP/1300198518MaRDI QIDQ2996575zbMATH OpenFDO

Authors Nicolas Curien, Adrien Joseph

Publication date 3 May 2011

Published in Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainquadtreeintegral equationcouplingpartial match queryfragmentation theory

Mathematics Subject Classification ID

Data structures (68P05) Discrete-time Markov processes on general state spaces (60J05) Limit theorems in probability theory (60F99)

Abstract: We analyze the mean cost of the partial match queries in random two-dimensional quadtrees. The method is based on fragmentation theory. The convergence is guaranteed by a coupling argument of Markov chains, whereas the value of the limit is computed as the fixed point of an integral equation.

Recommendations

• Partial Match Queries in Random Quadtrees
• Partial match queries in random quadtrees
• Limit laws for partial match queries in quadtrees
• A limit process for partial match queries in random quadtrees and 2-d trees
• Strong convergence of partial match queries in random quadtrees

Cites work

• Analytic combinatorics
• Analytic variations on quadtrees
• Asymptotic laws for nonconservative self-similar fragmentations
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• Hypergeometrics and the cost structure of quadtrees
• Integro-differential equations and generalized hypergeometric functions
• Markov Chains and Stochastic Stability
• Partial Match Queries in Random Quadtrees
• Quad trees: A data structure for retrieval by composite keys
• Random Fragmentation and Coagulation Processes
• Random recursive triangulations of the disk via fragmentation theory
• Sur Une Équation Fonctionnelle Et SES Applications: Une Extension Du Théorème De Kesten-Stigum Concernant Des Processus De Branchement

Cited in

(15)

• Partial match queries in random quadtrees
• A limit process for partial match queries in random quadtrees and 2-d trees
• Fixed partial match queries in quadtrees
• Limit laws for partial match queries in quadtrees
• A limit field for orthogonal range searches in two-dimensional random point search trees
• On a functional contraction method
• Partial Match Queries in Random Quadtrees
• Selection by rank in K-dimensional binary search trees
• Expected worst-case partial match in random quadtries
• On the cost of fixed partial match queries in \(K\)-d trees
• The dual tree of a recursive triangulation of the disk
• Psi-series method for equality of random trees and quadratic convolution recurrences
• On the expected cost of partial match queries in random quad-\(K\)-d trees
• Analytic variations on quadtrees
• Strong convergence of partial match queries in random quadtrees

This page was built for publication: Partial match queries in two-dimensional quadtrees: a probabilistic approach

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