TY - GEN
T1 - Robust proximity search for balls using sublinear space
AU - Har-Peled, Sariel
AU - Kumar, Nirman
PY - 2014/12/1
Y1 - 2014/12/1
N2 - Given a set of n disjoint balls b1, . . . , bn in ℝd, we provide a data structure, of near linear size, that can answer (1 ±ε)-approximate kth-nearest neighbor queries in O(log n + 1/εd) time, where k and ε are provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries, that requires (roughly) O(n/k) space; that is, the data structure has sublinear space requirement if k is sufficiently large.
AB - Given a set of n disjoint balls b1, . . . , bn in ℝd, we provide a data structure, of near linear size, that can answer (1 ±ε)-approximate kth-nearest neighbor queries in O(log n + 1/εd) time, where k and ε are provided at query time. If k and ε are provided in advance, we provide a data structure to answer such queries, that requires (roughly) O(n/k) space; that is, the data structure has sublinear space requirement if k is sufficiently large.
KW - Algorithms
KW - Approximate nearest neighbors
KW - Data structures
UR - http://www.scopus.com/inward/record.url?scp=84921519692&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84921519692&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2014.315
DO - 10.4230/LIPIcs.FSTTCS.2014.315
M3 - Conference contribution
AN - SCOPUS:84921519692
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 315
EP - 326
BT - 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014
A2 - Raman, Venkatesh
A2 - Suresh, S. P.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2014
Y2 - 15 December 2014 through 17 December 2014
ER -