@inproceedings{c4e929c74f0d4c41aa5caf901511dbbb,
title = "Space-time tradeoffs for proximity searching in doubling spaces",
abstract = "We consider approximate nearest neighbor searching in metric spaces of constant doubling dimension. More formally, we are given a set S of n points and an error bound ε > 0. The objective is to build a data structure so that given any query point q in the space, it is possible to efficiently determine a point of S whose distance from q is within a factor of (1 + ε) of the distance between q and its nearest neighbor in S. In this paper we obtain the following space-time tradeoffs. Given a parameter γ ε [2,1/ε], we show how to construct a data structure of space nγO(dim) log(1/ε) space that can answer queries in time O(log(nγ))+(1/(εγ))O(dim). This is the first result that offers space-time tradeoffs for approximate nearest neighbor queries in doubling spaces. At one extreme it nearly matches the best result currently known for doubling spaces, and at the other extreme it results in a data structure that can answer queries in time O(log(n/ε)), which matches the best query times in Euclidean space. Our approach involves a novel generalization of the AVD data structure from Euclidean space to doubling space.",
author = "Sunil Arya and Mount, {David M.} and Antoine Vigneron and Jian Xia",
year = "2008",
doi = "10.1007/978-3-540-87744-8_10",
language = "English (US)",
isbn = "3540877436",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "112--123",
booktitle = "Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings",
address = "Germany",
note = "16th Annual European Symposium on Algorithms, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",
}