Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T04:13:07.583Z Has data issue: false hasContentIssue false
  • English
  • Français

Strong Convergence of Partial Match Queries in Random Quadtrees

Published online by Cambridge University Press:  27 April 2012

NICOLAS CURIEN
NICOLAS CURIEN*
Affiliation:
Département de Mathématiques et Applications, École Normale Supérieure, 45 rue d'Ulm, 75230 Paris CEDEX 05, France (e-mail: nicolas.curien@ens.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Primary 60F9960G4460G1868W40

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 5 , September 2012 , pp. 683 - 694
Copyright
Copyright © Cambridge University Press 2012

References

[1]Bertoin, J. (2006) Random Fragmentations and Coagulation Processes, Vol. 102 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[2]Bertoin, J. (2008) Homogeneous multitype fragmentations. In In and Out of Equilibrium 2, Birkhäuser, Progr. Probab. 60 161–183.Google Scholar
[3]Bertoin, J. and Gnedin, A. (2004) Asymptotic laws for nonconservative self-similar fragmentations. Electron. J. Probab. 9 575–593.CrossRefGoogle Scholar
[4]Broutin, N., Neininger, R. and Sulzbach, H. (2012) A limit process for partial match queries in random quadtrees. Submitted. arXiv:abs/1202.1342Google Scholar
[5]Broutin, N., Neininger, R. and Sulzbach, H. (2012) Partial match queries in random quadtrees. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (Rabani, Y., ed.), pp. 1056–1065. arXiv:abs/1107.2231Google Scholar
[6]Curien, N. and Joseph, A. (2011) Partial match queries in random quadtrees: A probabilistic approach. Adv. Appl. Probab. 43 178–194.CrossRefGoogle Scholar
[7]Curien, N. and Le Gall, J.-F. (2011) Random recursive triangulations of the disk via fragmentation theory. Ann. Probab. 39 2224–2270.CrossRefGoogle Scholar
[8]Finkel, R. A. and Bentley, J. L. (1974) Quad trees: A data structure for retrieval on composite keys. Acta Informatica 4 1–9.CrossRefGoogle Scholar
[9]Flajolet, P., Gonnet, G., Puech, C. and Robson, J. M. (1993) Analytic variations on quadtrees. Algorithmica 10 473–500.CrossRefGoogle Scholar
[10]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar