TY - GEN

T1 - Orthogonal range searching in moderate dimensions

T2 - 33rd International Symposium on Computational Geometry, SoCG 2017

AU - Chan, Timothy M.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - 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(n1+δ) for any constant δ > 0, and the expected query time is n1-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 n2-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 ℓ∞ nearest neighbor search when d = c log n.

AB - 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(n1+δ) for any constant δ > 0, and the expected query time is n1-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 n2-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 ℓ∞ nearest neighbor search when d = c log n.

KW - Computational geometry

KW - Data structures

KW - Nearest neighbor searching

KW - Range searching

UR - http://www.scopus.com/inward/record.url?scp=85029939178&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029939178&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2017.27

DO - 10.4230/LIPIcs.SoCG.2017.27

M3 - Conference contribution

AN - SCOPUS:85029939178

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 271

EP - 2715

BT - 33rd International Symposium on Computational Geometry, SoCG 2017

A2 - Katz, Matthew J.

A2 - Aronov, Boris

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 4 July 2017 through 7 July 2017

ER -