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

DOI10.1239/aap/1300198518zbMath1215.68083arXiv1009.3113MaRDI QIDQ2996575

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

quadtree; integral equation; Markov chain; coupling; partial match query; fragmentation theory

Mathematics Subject Classification ID

60J05: Discrete-time Markov processes on general state spaces

68P05: Data structures

60F99: Limit theorems in probability theory

Related Items

Fixed Partial Match Queries in Quadtrees, 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, A limit field for orthogonal range searches in two-dimensional random point search trees, The dual tree of a recursive triangulation of the disk, On a functional contraction method, Psi-series method for equality of random trees and quadratic convolution recurrences, Selection by rank inK-dimensional binary search trees, Strong Convergence of Partial Match Queries in Random Quadtrees

Cites Work

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