2026-07-23T00:23:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4852 2024-03-06T10:35:26Z ddc:004 open_access

Robust Proximity Search for Balls Using Sublinear Space Har-Peled, Sariel Kumar, Nirman Approximate Nearest neighbors algorithms data structures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sariel Har-Peled and Nirman Kumar 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.315 urn:nbn:de:0030-drops-48526 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.315 eng https://creativecommons.org/licenses/by/3.0/legalcode