Chan, Timothy M.
Orthogonal Range Searching in Moderate Dimensions: kd Trees and Range Trees Strike Back
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^{11/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 kd 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 allpairs shortest paths in general realweighted 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^{21/O(log c)}time noncombinatorial 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.
BibTeX  Entry
@InProceedings{chan:LIPIcs:2017:7226,
author = {Timothy M. Chan},
title = {{Orthogonal Range Searching in Moderate Dimensions: kd Trees and Range Trees Strike Back}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {27:127:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7226},
URN = {urn:nbn:de:0030drops72262},
doi = {10.4230/LIPIcs.SoCG.2017.27},
annote = {Keywords: computational geometry, data structures, range searching, nearest neighbor searching}
}
2017
Keywords: 

computational geometry, data structures, range searching, nearest neighbor searching 
Seminar: 

33rd International Symposium on Computational Geometry (SoCG 2017)

Issue date: 

2017 
Date of publication: 

2017 