Robust proximity search for balls using sublinear space
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- scientific article; zbMATH DE number 2119656 (Why is no real title available?)
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Approximate nearest neighbor: towards removing the curse of dimensionality
- Approximate range searching
- Approximating Minimization Diagrams and Generalized Proximity Search
- Down the rabbit hole: robust proximity search and density estimation in sublinear space
- Geographic quorum system approximations
- Geometric approximation algorithms
- Robust proximity search for balls using sublinear space
- Space-time tradeoffs for approximate nearest neighbor searching
- Space-time tradeoffs for approximate spherical range counting
- Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
Cited in
(3)
This page was built for publication: Robust proximity search for balls using sublinear space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702130)
