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

Research output: Contribution to journalArticlepeer-review

Abstract

We revisit the orthogonal range searching problem and the exact ℓ 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 + δ ) for any constant δ> 0 , and the expected query time is n 1 - 1 / O ( c log c ) for d= clog 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 et al. in arXiv:1401.5512, 2014) and (Chan in Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015)]. 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 et al. in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015]. 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 (J Comput Syst Sci 63(4):627–638, 2001) for approximateℓ nearest neighbor search when d= clog n.

Original languageEnglish (US)
Pages (from-to)899-922
Number of pages24
JournalDiscrete and Computational Geometry
Volume61
Issue number4
DOIs
StatePublished - Jun 15 2019

Keywords

  • All-pairs shortest paths
  • Boolean matrix multiplication
  • Geometric data structures
  • Nearest neighbor searching
  • Range searching
  • Range trees
  • k-d trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back'. Together they form a unique fingerprint.

Cite this