Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Har-Peled, Sariel; Kumar, Nirman http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-48526
URL:

;

Robust Proximity Search for Balls Using Sublinear Space

pdf-format:


Abstract

Given a set of n disjoint balls b_1, ..., b_n in R^d, we provide a data structure, of near linear size, that can answer (1 +- epsilon)-approximate k-th-nearest neighbor queries in O(log(n) + 1/epsilon^d) time, where k and epsilon are provided at query time. If k and epsilon are provided in advance, we provide a data structure to answer such queries, that requires (roughly) O(n/k) space; that is, the data structure has sublinear space requirement if k is sufficiently large.

BibTeX - Entry

@InProceedings{harpeled_et_al:LIPIcs:2014:4852,
  author =	{Sariel Har-Peled and Nirman Kumar},
  title =	{{Robust Proximity Search for Balls Using Sublinear Space}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{315--326},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4852},
  URN =		{urn:nbn:de:0030-drops-48526},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.315},
  annote =	{Keywords: Approximate Nearest neighbors, algorithms, data structures}
}

Keywords: Approximate Nearest neighbors, algorithms, data structures
Seminar: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue date: 2014
Date of publication: 2014


DROPS-Home | Fulltext Search | Imprint Published by LZI