Strong convergence of partial match queries in random quadtrees

DOI10.1017/S096354831200017XMaRDI QIDQ2911068zbMATH OpenFDO

Authors Nicolas Curien

Publication date 12 September 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

random recursive constructionself-similar fragmentations

Mathematics Subject Classification ID

Limit theorems in probability theory (60F99) Self-similar stochastic processes (60G18) Martingales with continuous parameter (60G44) Information storage and retrieval of data (68P20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

Abstract: We prove that the rescaled costs of partial match queries in a random two-dimensional quadtree converge almost surely towards a random limit which is identified as the terminal value of a martingale. Our approach shares many similarities with the theory of self-similar fragmentations.

Recommendations

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

Cites work

• Analytic variations on quadtrees
• Asymptotic laws for nonconservative self-similar fragmentations
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Quad trees: A data structure for retrieval by composite keys
• Random recursive triangulations of the disk via fragmentation theory

Cited in

(6)

• Limit laws for partial match queries in quadtrees
• A limit field for orthogonal range searches in two-dimensional random point search trees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Partial Match Queries in Random Quadtrees
• On the number of large triangles in the Brownian triangulation and fragmentation processes
• Refined asymptotics for the number of leaves of random point quadtrees

This page was built for publication: Strong convergence of 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 Q2911068)