License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.315
URN: urn:nbn:de:0030-drops-48526
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4852/
Har-Peled, Sariel ;
Kumar, Nirman
Robust Proximity Search for Balls Using Sublinear Space
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 |
|
Collection: |
|
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
12.12.2014 |
