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 -