Abstract
In this work we present an in-depth study of randomized relaxed K-d trees. It covers two fundamental aspects: the randomized algorithms that allow to preserve the random properties of relaxed K-d trees and the mathematical analysis of the expected performance of these algorithms.
In particular, we describe randomized update algorithms for K-d trees based on the split and join algorithms of Duch et al. [1998]. We carry out an analysis of the expected cost of all these algorithms, using analytic combinatorics techniques. We show that the average cost of split and join is of the form ζ(K) ⋅ nϕ(K) + o(nϕ(K)), with 1 ≤ ϕ(K) < 1.561552813, and we give explicit formulæ for both ζ(K) and ϕ(K). These results on the average performance of split and join imply that the expected cost of an insertion or a deletion is Θ(nϕ(K)−1) when K > 2 and Θ(log n) for K = 2.
- Abramowitz, M., and Stegun, I. A. 1964. Handbook of Mathematical Functions. Dover. Google ScholarDigital Library
- Aragon, C. R., and Seidel, R. G. 1996. Randomized search trees. Algorithmica 16, 464--497.Google ScholarCross Ref
- Bentley, J. L. 1975. Multidimensional binary search trees used for associative retrieval. Comm. ACM 18, 9, 509--517. Google ScholarDigital Library
- Broutin, N., Dalal, K., Devroye, L., and McLeish, E. 2006. The k-d treap. Personal communication.Google Scholar
- Chanzy, P., Devroye, L., and Zamora-Cura, C. 2001. Analysis of range search for random k-d trees. Acta Inf. 37, 355--383. Google ScholarDigital Library
- Devroye, L., Jabbour, J., and Zamora-Cura, C. 2000. Squarish k-d trees. SIAM J. Comput. 30, 1678--1700. Google ScholarDigital Library
- Duch, A., Estivill-Castro, V., and Martínez, C. 1998. Randomized K-dimensional binary search trees. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC'98), K.-Y. Chwa and O. H. Ibarra, Eds. Lecture Notes in Computer Science, vol. 1533. Springer-Verlag, 199--208. Google ScholarDigital Library
- Duch, A., and Martínez, C. 2002. On the average performance of orthogonal range search in multidimensional data structures. J. Algor. 44, 1, 226--245. Google ScholarDigital Library
- Duch, A., and Martínez, C. 2007. On the average cost of insertions on random relaxed k-d trees. In Proceedings of the 9th ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX) and the 4th ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick, Eds. SIAM, 194--200.Google Scholar
- Flajolet, P., and Odlyzko, A. 1990. Singularity analysis of generating functions. SIAM J. Discr. Math. 3, 1, 216--240.Google ScholarCross Ref
- Flajolet, P., and Puech, C. 1986. Partial match retrieval of multidimensional data. J. ACM 33, 2, 371--407. Google ScholarDigital Library
- Flajolet, P., and Sedgewick, R. 2008. Analytic Combinatorics. Cambridge University Press. Google ScholarDigital Library
- Graham, R. L., Knuth, D. E., and Patashnik, O. 1994. Concrete Mathematics 2nd Ed. Addison--Wesley.Google Scholar
- Knuth, D. E. 1997. The Art of Computer Programming: Fundamental Algorithms 3rd Ed. Vol. 1. Addison--Wesley. Google ScholarDigital Library
- Knuth, D. E. 1998a. The Art of Computer Programming: Seminumerical Algorithms 3rd Ed. Vol. 2. Addison--Wesley. Google ScholarDigital Library
- Knuth, D. E. 1998b. The Art of Computer Programming: Sorting and Searching 2nd Ed. Vol. 3. Addison--Wesley. Google ScholarDigital Library
- Martínez, C., Panholzer, A., and Prodinger, H. 2001. Partial match queries in relaxed multidimensional search trees. Algorithmica 29, 1--2, 181--204.Google ScholarDigital Library
- Martínez, C., and Roura, S. 1998. Randomized binary search trees. J. ACM 45, 2, 288--323. Google ScholarDigital Library
- Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press. Google ScholarDigital Library
- Roura, S. 2001. Improved master theorems for divide-and-conquer recurrences. J. ACM 48, 2, 170--205. Google ScholarDigital Library
- Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley. Google ScholarDigital Library
- Szpankowski, W. 2001. Average Case Analysis of Algorithms on Sequences. John Wiley & Sons. Google ScholarDigital Library
Index Terms
Updating relaxed K-d trees
Recommendations
Median and Hybrid Median K-Dimensional Trees
LATIN 2022: Theoretical InformaticsAbstractWe consider here two new variants of K-dimensional binary search trees (K-d trees): median K-d trees and hybrid-median K-d trees. These two kinds of trees are designed with the aim to get a tree as balanced as possible. This goal is attained by ...
Randomized splay trees: theoretical and experimental results
Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy ...
Estimating the weight of metric minimum spanning trees in sublinear-time
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingIn this paper we present a sublinear time (1 + ε)-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n-point metric space. The running time of the algorithm is Û(n/εO(1)). Since the full description of an n-...
Comments