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

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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Pages112-123
Number of pages12
Volume5193 LNCS
DOIs
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

Other

Other16th Annual European Symposium on Algorithms, ESA 2008
CountryGermany
CityKarlsruhe
Period09/15/0809/17/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this