zbMATH — the first resource for mathematics

A limit field for orthogonal range searches in two-dimensional random point search trees. (English) Zbl 1422.60020
Summary: We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. We also state similar results for 2-d trees. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an open question of P. Chanzy et al. [Acta Inf. 37, No. 4–5, 355–383 (2001; Zbl 0970.68046)].
60C05 Combinatorial probability
60F17 Functional limit theorems; invariance principles
68P20 Information storage and retrieval of data
60D05 Geometric probability and stochastic geometry
60G60 Random fields
Full Text: DOI arXiv
[1] Bentley, J. L., Multidimensional binary search trees used for associative searching, Commun. ACM, 18, 509-517, (1975) · Zbl 0306.68061
[2] Bentley, J. L., Decomposable searching problems, Inform. Process. Lett., 8, 5, 244-251, (1979) · Zbl 0404.68067
[3] Bentley, J. L.; Friedman, J. H., Data structures for range searching, ACM Comput. Surv., 11, 397-409, (1979)
[4] Billingsley, P., (Convergence of Probability Measures. Convergence of Probability Measures, Wiley Series in Probability and Mathematical Statistics, (1999), Wiley)
[5] Broutin, N.; Neininger, R.; Sulzbach, H., Partial match queries in random quadtrees, (Proceedings of the Twenty-THird Annual ACM-SIAM Symposium on Discrete Algorithms, (2012), ACM: ACM New York), 1056-1065 · Zbl 1420.68079
[6] Broutin, N.; Neininger, R.; Sulzbach, H., A limit process for partial match queries in random quadtrees and \(2\)-d trees, Ann. Appl. Probab., 23, 6, 2560-2603, (2013) · Zbl 1358.68080
[7] Broutin, N.; Sulzbach, H., The dual tree of a recursive triangulation of the disk, Ann. Probab., 43, 2, 738-781, (2015) · Zbl 1355.60014
[8] Chanzy, P.; Devroye, L.; Zamora-Cura, C., Analysis of range search for random k-d trees, Acta Inform., 37, 355-383, (2001) · Zbl 0970.68046
[9] Chern, H.-H.; Hwang, H.-K., Partial match queries in random quadtrees, SIAM J. Comput., 32, 904-915, (2003) · Zbl 1053.68128
[10] Chern, H.-H.; Hwang, H.-K., Partial match queries in random \(k\)-d trees, SIAM J. Comput., 35, 1440-1466, (2006) · Zbl 1116.68029
[11] Curien, N., Strong convergence of partial match queries in random quadtrees, Combin. Probab. Comput., 21, 5, 683-694, (2012) · Zbl 1252.68100
[12] Curien, N.; Joseph, A., Partial match queries in two-dimensional quadtrees: A probabilistic approach, Adv. Appl. Probab., 43, 178-194, (2011) · Zbl 1215.68083
[13] Devroye, L., Branching processes in the analysis of the heights of trees, Acta Inform., 24, 277-298, (1987) · Zbl 0643.60065
[14] Devroye, L., Universal limit laws for depth in random trees, SIAM J. Comput., 28, 2, 409-432, (1998) · Zbl 0915.68089
[15] Devroye, L.; Jabbour, J.; Zamora-Cura, C., Squarish \(k\)-d trees, SIAM J. Comput., 30, 1678-1700, (2001) · Zbl 0977.68024
[16] Devroye, L.; Laforest, L., An analysis of \(d\)-dimensional quad trees, SIAM J. Comput., 19, 821-832, (1990) · Zbl 0711.68032
[17] Duch, A.; Estivill-Castro, V.; Martínez, C., Randomized \(k\)-dimensional binary search trees, (Chwa, K. Y.; Ibarra, O., Proc. of the 9th International Symposium on Algorithms and Computation. Proc. of the 9th International Symposium on Algorithms and Computation, (ISAAC’98). Proc. of the 9th International Symposium on Algorithms and Computation. Proc. of the 9th International Symposium on Algorithms and Computation, (ISAAC’98), Lecture Notes in Computer Science, vol. 1533, (1998), Springer Verlag), 199-208
[18] Duch, A.; Martínez, C., On the average performance of orthogonal range search in multidimensional data structures, J. Algorithms, 44, 1, 226-245, (2002) · Zbl 1010.68048
[19] Dunford, N.; Schwartz, J. T., (Linear Operators. I. General Theory. Linear Operators. I. General Theory, With the assistance of W. G. Bade and R. G. Bartle. Pure and Applied Mathematics, vol. 7, (1958), Interscience Publishers, Inc., Interscience Publishers, Ltd.: Interscience Publishers, Inc., Interscience Publishers, Ltd. New York, London), xiv+858 · Zbl 0635.47001
[20] Dvoretzky, A.; Kiefer, J.; Wolfowitz, J., Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, Ann. Math. Stat., 27, 642-669, (1956) · Zbl 0073.14603
[21] Finkel, R. A.; Bentley, J. L., Quad trees, a data structure for retrieval on composite keys, Acta Inform., 4, 1-19, (1974) · Zbl 0278.68030
[22] Flajolet, P.; Gonnet, G. H.; Puech, C.; Robson, J. M., Analytic variations on quadtrees, Algorithmica, 10, 473-500, (1993) · Zbl 0783.68056
[23] Flajolet, P.; Labelle, G.; Laforest, L.; Salvy, B., Hypergeometrics and the cost structure of quadtrees, Random Structures Algorithms, 7, 117-144, (1995) · Zbl 0834.68013
[24] Flajolet, P.; Lafforgue, T., Search costs in quadtrees and singularity perturbation asymptotics, Discrete Comput. Geom., 12, 151-175, (1994)
[25] Flajolet, P.; Puech, C., Partial match retrieval of multidimensional data, J. Assoc. Comput. Mach., 33, 2, 371-407, (1986)
[26] Kiefer, J.; Wolfowitz, J., On the deviations of the empiric distribution function of vector chance variables, Trans. Amer. Math. Soc., 87, 173-186, (1958) · Zbl 0088.11305
[27] Kirk, W. A., Contraction mappings and extensions, (Handbook of Metric Fixed Point Theory, (2001), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 1-34 · Zbl 1019.54001
[28] Neininger, R.; Rüschendorf, L., A general limit theorem for recursive algorithms and combinatorial structures, Ann. Appl. Probab., 14, 1, 378-418, (2004) · Zbl 1041.60024
[29] Neininger, R.; Sulzbach, H., On a functional contraction method, Ann. Probab., 43, 4, 1777-1822, (2015) · Zbl 1372.60045
[30] Rachev, S.; Rüschendorf, L., Probability metrics and recursive algorithms, Adv. Appl. Probab., 27, 770-799, (1995) · Zbl 0829.60094
[31] Rösler, U., A limit theorem for “Quicksort”, RAIRO Inform. Théor. Appl., 25, 85-100, (1991) · Zbl 0718.68026
[32] Rösler, U., A fixed point theorem for distributions, Stochastic Process. Appl., 37, 195-214, (1992) · Zbl 0761.60015
[33] Rösler, U.; Rüschendorf, L., The contraction method for recursive algorithms, Algorithmica, 29, 3-33, (2001) · Zbl 0967.68166
[34] Samet, H., Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, (1990), Addison-Wesley: Addison-Wesley Reading, MA
[35] Samet, H., The Design and Analysis of Spatial Data Structures, (1990), Addison-Wesley: Addison-Wesley Reading, MA
[36] Samet, H., Foundations of Multidimensional and Metric Data Structures, (2006), Morgan Kaufmann · Zbl 1139.68022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.