Space-time tradeoffs for proximity searching in doubling spaces

Sunil Arya*, David M. Mount, Antoine Vigneron, Jian Xia

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540877436, 9783540877431
StatePublished - 2008
Externally publishedYes
Event16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany
Duration: Sep 15 2008Sep 17 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5193 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th Annual European Symposium on Algorithms, ESA 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Space-time tradeoffs for proximity searching in doubling spaces'. Together they form a unique fingerprint.

Cite this