TY - GEN

T1 - Space-time tradeoffs for proximity searching in doubling spaces

AU - Arya, Sunil

AU - Mount, David M.

AU - Vigneron, Antoine

AU - Xia, Jian

PY - 2008

Y1 - 2008

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

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

UR - http://www.scopus.com/inward/record.url?scp=57749184729&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-87744-8-10

DO - 10.1007/978-3-540-87744-8-10

M3 - Conference contribution

AN - SCOPUS:57749184729

SN - 3540877436

SN - 9783540877431

VL - 5193 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 112

EP - 123

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

T2 - 16th Annual European Symposium on Algorithms, ESA 2008

Y2 - 15 September 2008 through 17 September 2008

ER -