TY - GEN
T1 - Searching dynamic point sets in spaces with bounded doubling dimension
AU - Cole, Richard
AU - Gottlieb, Lee Ad
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 - https://www.scopus.com/pages/publications/33748092859
U2 - 10.1145/1132516.1132599
DO - 10.1145/1132516.1132599
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
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
T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06
Y2 - 21 May 2006 through 23 May 2006
ER -