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

DOI10.1137/130916448MaRDI QIDQ2929705zbMATH OpenOpenAlexFDO

Authors Nirman Kumar, Sariel Har-Peled

Publication date 14 November 2014

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

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

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)

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.

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

Cited in

(5)

• LiNearN: a new approach to nearest neighbour density estimator
• Nearest-neighbor searching under uncertainty. I
• On clustering induced Voronoi diagrams
• Robust proximity search for balls using sublinear space
• 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)