TY - GEN
T1 - Searching dynamic point sets in spaces with bounded doubling dimension
AU - Cole, Richard
AU - Gottlieb, Lee Ad
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1 + ε)-approximate nearest neighbor in time O(log n) + (1/ε)O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.
AB - We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1 + ε)-approximate nearest neighbor in time O(log n) + (1/ε)O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.
KW - Approximate nearest neighbor search
UR - http://www.scopus.com/inward/record.url?scp=33748092859&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748092859&partnerID=8YFLogxK
U2 - 10.1145/1132516.1132599
DO - 10.1145/1132516.1132599
M3 - Conference contribution
AN - SCOPUS:33748092859
SN - 1595931341
SN - 9781595931344
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 574
EP - 583
BT - STOC'06
PB - Association for Computing Machinery
T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06
Y2 - 21 May 2006 through 23 May 2006
ER -