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

DOI10.1239/AAP/1300198518zbMATH Open1215.68083arXiv1009.3113MaRDI QIDQ2996575FDOQ2996575

Authors: Nicolas Curien, Adrien Joseph 

Publication date: 3 May 2011

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

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.

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

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

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)

Cites Work

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

Cited In (15)

• The dual tree of a recursive triangulation of the disk
• Analytic variations on quadtrees
• 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
• 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
• Partial Match Queries in Random Quadtrees
• Expected worst-case partial match in random quadtries
• Selection by rank in K-dimensional binary search trees
• 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

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)