@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",

}