@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",
note = "38th Annual ACM Symposium on Theory of Computing, STOC'06 ; Conference date: 21-05-2006 Through 23-05-2006",
}