Document Open Access Logo

Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

Author Timothy M. Chan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.27.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Timothy M. Chan

Cite As Get BibTex

Timothy M. Chan. Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.27

Abstract

We revisit the orthogonal range searching problem and the exact l_infinity nearest neighbor searching problem for a static set of n points when the dimension d is moderately large. We give the first data structure with near linear space that achieves truly sublinear query time when the dimension is any constant multiple of log n.  Specifically, the preprocessing time and space are O(n^{1+delta}) for any constant delta>0, and the expected query time is n^{1-1/O(c log c)} for d = c log n.  The data structure is simple and is based on a new "augmented, randomized, lopsided" variant of k-d trees.  It matches (in fact, slightly improves) the performance of previous combinatorial algorithms that work only in the case of offline queries [Impagliazzo, Lovett, Paturi, and Schneider (2014) and Chan (SODA'15)]. It leads to slightly faster combinatorial algorithms for all-pairs shortest paths in general real-weighted graphs and rectangular Boolean matrix multiplication.

In the offline case, we show that the problem can be reduced to the Boolean orthogonal vectors problem and thus admits an n^{2-1/O(log c)}-time non-combinatorial algorithm [Abboud, Williams, and Yu (SODA'15)]. This reduction is also simple and is based on range trees.

Finally, we use a similar approach to obtain a small improvement to Indyk's data structure [FOCS'98] for approximate l_infinity nearest neighbor search when d = c log n.

Subject Classification

Keywords
  • computational geometry
  • data structures
  • range searching
  • nearest neighbor searching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proc. 26th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 218-230, 2015. Google Scholar
  2. Peyman Afshani, Timothy M. Chan, and Konstantinos Tsakalidis. Deterministic rectangle enclosure and offline dominance reporting on the RAM. In Proc. 41st Int'l Colloq. Automata, Languages, and Programming (ICALP), Part I, pages 77-88, 2014. Google Scholar
  3. Josh Alman, Timothy M. Chan, and Ryan Williams. Polynomial representation of threshold functions with applications. In Proc. 57th IEEE Symp. Found. Comput. Sci. (FOCS), pages 467-476, 2016. Google Scholar
  4. Josh Alman and Ryan Williams. Probabilistic polynomials and Hamming nearest neighbors. In Proc. 56th IEEE Symp. Found. Comput. Sci. (FOCS), pages 136-150, 2015. Google Scholar
  5. Alexandr Andoni, Dorian Croitoru, and Mihai M. Pătraşcu. Hardness of nearest neighbor under L_∞. In Proc. 49th IEEE Symp. Found. Comput. Sci. (FOCS), pages 424-433, 2008. Google Scholar
  6. V. Z. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzhev. On economical construction of the transitive closure of a directed graph. Soviet Mathematics Doklady, 11:1209-1210, 1970. Google Scholar
  7. Timothy M. Chan. Geometric applications of a randomized optimization technique. Discrete Comput. Geom., 22(4):547-567, 1999. Google Scholar
  8. Timothy M. Chan. Speeding up the Four Russians algorithm by about one more logarithmic factor. In Proc. 26th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 212-217, 2015. Google Scholar
  9. Timothy M. Chan and Ryan Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In Proc. 27th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 1246-1255, 2016. Google Scholar
  10. T. M. Chan. All-pairs shortest paths with real weights in O(n³/log n) time. Algorithmica, 50:236-243, 2008. Google Scholar
  11. T. M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput., 39:2075-2089, 2010. Google Scholar
  12. T. M. Chan, K. G. Larsen, and M. Pătraşcu. Orthogonal range searching on the RAM, revisited. In Proc. 27th ACM Symp. Comput. Geom. (SoCG), pages 1-10, 2011. Google Scholar
  13. T. M. Chan and M. Pătraşcu. Counting inversions, offline orthogonal range counting, and related problems. In Proc. 21st ACM-SIAM Symp. Discrete Algorithms (SODA), pages 161-173, 2010. Google Scholar
  14. Daniel M. Gordon, Oren Patashnik, Greg Kuperberg, and Joel Spencer. Asymptotically optimal covering designs. J. Combinatorial Theory, Series A, 75(2):270-280, 1996. Google Scholar
  15. Y. Han and T. Takaoka. An O(n³log log n/log²n) time algorithm for all pairs shortest paths. In Proc. 13th Scand. Symp. and Workshops on Algorithm Theory (SWAT), pages 131-141, 2012. Google Scholar
  16. Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory Comput., 8(1):321-350, 2012. Google Scholar
  17. R. Impagliazzo, S. Lovett, R. Paturi, and S. Schneider. 0-1 integer linear programming with a linear number of constraints, 2014. Google Scholar
  18. Piotr Indyk. On approximate nearest neighbors under l_∞ norm. J. Comput. Sys. Sci., 63(4):627-638, 2001. Google Scholar
  19. Kasper Green Larsen and Ryan Williams. Faster online matrix-vector multiplication. In Proc. 28th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 2182-2189, 2017. Google Scholar
  20. François Le Gall. Faster algorithms for rectangular matrix multiplication. In Proc. 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 514-523, 2012. Google Scholar
  21. Jirí Matoušek. Computing dominances in Eⁿ. Inform. Process. Lett., 38(5):277-278, 1991. Google Scholar
  22. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985. Google Scholar
  23. R. Williams. Faster all-pairs shortest paths via circuit complexity. In Proc. 46th ACM Symp. Theory Comput. (STOC), pages 664-673, 2014. Google Scholar
  24. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Google Scholar
  25. Ryan Williams. Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In Proc. 18th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 995-1001, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283490.
  26. Huacheng Yu. An improved combinatorial algorithm for Boolean matrix multiplication. In Proc. 42nd Int'l Colloq. Automata, Languages, and Programming (ICALP), Part I, pages 1094-1105, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact