Affordable Access

Robust Proximity Search for Balls using Sublinear Space

Authors
  • Har-Peled, Sariel
  • Kumar, Nirman
Type
Preprint
Publication Date
Oct 29, 2014
Submission Date
Jan 07, 2014
Identifiers
arXiv ID: 1401.1472
Source
arXiv
License
Yellow
External links

Abstract

Given a set of n disjoint balls b1, . . ., bn in IRd, we provide a data structure, of near linear size, that can answer (1 \pm \epsilon)-approximate kth-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.

Report this publication

Statistics

Seen <100 times