Down the rabbit hole: robust proximity search and density estimation in sublinear space

DOI10.1137/130916448zbMATH Open1302.68318arXiv1111.2942OpenAlexW2176844258MaRDI QIDQ2929705FDOQ2929705

Authors: Nirman Kumar, Sariel Har-Peled 

Publication date: 14 November 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: For a set of $n$ points in $R{e}^d$, and parameters $k$ and $eps$, we present a data structure that answers $(1+eps,k)$-ANN queries in logarithmic time. Surprisingly, the space used by the data-structure is $Otilde(n/k)$; that is, the space used is sublinear in the input size if $k$ is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch. Using this, we provide a sublinear space data-structure that can estimate the density of a point set under various measures, including: �egin{inparaenum}[(i)] item sum of distances of $k$ closest points to the query point, and item sum of squared distances of $k$ closest points to the query point. end{inparaenum} Our approach generalizes to other distance based estimation of densities of similar flavor. We also study the problem of approximating some of these quantities when using sampling. In particular, we show that a sample of size $Otilde(n/k)$ is sufficient, in some restricted cases, to estimate the above quantities. Remarkably, the sample size has only linear dependency on the dimension.

Full work available at URL: https://arxiv.org/abs/1111.2942

Recommendations

• Robust proximity search for balls using sublinear space
• Robust proximity search for balls using sublinear space
• Approximate \(k\)-flat nearest neighbor search
• Approximate nearest neighbor queries revisited
• scientific article; zbMATH DE number 437552

zbMATH Keywords

proximity search\(k\)th nearest neighborapproximate Voronoi diagramgeometric approximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (3)

• On Clustering Induced Voronoi Diagrams
• Nearest-neighbor searching under uncertainty. I
• Robust proximity search for balls using sublinear space

This page was built for publication: Down the rabbit hole: robust proximity search and density estimation in sublinear space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929705)