Searching dynamic point sets in spaces with bounded doubling dimension

Richard Cole; Lee Ad Gottlieb

doi:10.1145/1132516.1132599

Searching dynamic point sets in spaces with bounded doubling dimension

Richard Cole, Lee Ad Gottlieb

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	STOC'06
Subtitle of host publication	Proceedings of the 38th Annual ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Pages	574-583
Number of pages	10
ISBN (Print)	1595931341, 9781595931344
DOIs	https://doi.org/10.1145/1132516.1132599
State	Published - 2006
Event	38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States Duration: May 21 2006 → May 23 2006

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	2006
ISSN (Print)	0737-8017

Other

Other	38th Annual ACM Symposium on Theory of Computing, STOC'06
Country	United States
City	Seattle, WA
Period	5/21/06 → 5/23/06

Keywords

Approximate nearest neighbor search

ASJC Scopus subject areas

Software

Access to Document

10.1145/1132516.1132599

Fingerprint Dive into the research topics of 'Searching dynamic point sets in spaces with bounded doubling dimension'. Together they form a unique fingerprint.

Cite this

Searching dynamic point sets in spaces with bounded doubling dimension. / Cole, Richard; Gottlieb, Lee Ad.

STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2006. p. 574-583 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cole, R & Gottlieb, LA 2006, Searching dynamic point sets in spaces with bounded doubling dimension. in STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 2006, Association for Computing Machinery, pp. 574-583, 38th Annual ACM Symposium on Theory of Computing, STOC'06, Seattle, WA, United States, 5/21/06. https://doi.org/10.1145/1132516.1132599

@inproceedings{c87169abe0914d30853cddff9cd8e7c0,

title = "Searching dynamic point sets in spaces with bounded doubling dimension",

abstract = "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.",

keywords = "Approximate nearest neighbor search",

author = "Richard Cole and Gottlieb, {Lee Ad}",

year = "2006",

doi = "10.1145/1132516.1132599",

language = "English (US)",

isbn = "1595931341",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "574--583",

booktitle = "STOC'06",

}

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 - 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 -