skip to main content
research-article

Updating relaxed K-d trees

Published:28 December 2009Publication History
Skip Abstract Section

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.

References

  1. Abramowitz, M., and Stegun, I. A. 1964. Handbook of Mathematical Functions. Dover. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Aragon, C. R., and Seidel, R. G. 1996. Randomized search trees. Algorithmica 16, 464--497.Google ScholarGoogle ScholarCross RefCross Ref
  3. Bentley, J. L. 1975. Multidimensional binary search trees used for associative retrieval. Comm. ACM 18, 9, 509--517. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Broutin, N., Dalal, K., Devroye, L., and McLeish, E. 2006. The k-d treap. Personal communication.Google ScholarGoogle Scholar
  5. Chanzy, P., Devroye, L., and Zamora-Cura, C. 2001. Analysis of range search for random k-d trees. Acta Inf. 37, 355--383. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Devroye, L., Jabbour, J., and Zamora-Cura, C. 2000. Squarish k-d trees. SIAM J. Comput. 30, 1678--1700. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle Scholar
  10. Flajolet, P., and Odlyzko, A. 1990. Singularity analysis of generating functions. SIAM J. Discr. Math. 3, 1, 216--240.Google ScholarGoogle ScholarCross RefCross Ref
  11. Flajolet, P., and Puech, C. 1986. Partial match retrieval of multidimensional data. J. ACM 33, 2, 371--407. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Flajolet, P., and Sedgewick, R. 2008. Analytic Combinatorics. Cambridge University Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Graham, R. L., Knuth, D. E., and Patashnik, O. 1994. Concrete Mathematics 2nd Ed. Addison--Wesley.Google ScholarGoogle Scholar
  14. Knuth, D. E. 1997. The Art of Computer Programming: Fundamental Algorithms 3rd Ed. Vol. 1. Addison--Wesley. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Knuth, D. E. 1998a. The Art of Computer Programming: Seminumerical Algorithms 3rd Ed. Vol. 2. Addison--Wesley. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. Knuth, D. E. 1998b. The Art of Computer Programming: Sorting and Searching 2nd Ed. Vol. 3. Addison--Wesley. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Martínez, C., Panholzer, A., and Prodinger, H. 2001. Partial match queries in relaxed multidimensional search trees. Algorithmica 29, 1--2, 181--204.Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Martínez, C., and Roura, S. 1998. Randomized binary search trees. J. ACM 45, 2, 288--323. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Roura, S. 2001. Improved master theorems for divide-and-conquer recurrences. J. ACM 48, 2, 170--205. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Szpankowski, W. 2001. Average Case Analysis of Algorithms on Sequences. John Wiley & Sons. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Updating relaxed K-d trees

            Recommendations

            Comments

            Login options

            Check if you have access through your login credentials or your institution to get full access on this article.

            Sign in

            Full Access

            • Published in

              cover image ACM Transactions on Algorithms
              ACM Transactions on Algorithms  Volume 6, Issue 1
              December 2009
              374 pages
              ISSN:1549-6325
              EISSN:1549-6333
              DOI:10.1145/1644015
              Issue’s Table of Contents

              Copyright © 2009 ACM

              Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

              Publisher

              Association for Computing Machinery

              New York, NY, United States

              Publication History

              • Published: 28 December 2009
              • Received: 1 February 2009
              • Accepted: 1 February 2009
              Published in talg Volume 6, Issue 1

              Permissions

              Request permissions about this article.

              Request Permissions

              Check for updates

              Qualifiers

              • research-article
              • Research
              • Refereed

            PDF Format

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader