Proximity in the age of distraction: robust approximate nearest neighbor search

DOI10.1137/1.9781611974782.1zbMATH Open1410.68107arXiv1511.07357OpenAlexW2279110065MaRDI QIDQ4575733FDOQ4575733

Authors: Sepideh Mahabadi, Sariel Har-Peled 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We introduce a new variant of the nearest neighbor search problem, which allows for some coordinates of the dataset to be arbitrarily corrupted or unknown. Formally, given a dataset of $n$ points $P=x_1,ldots,x_n$ in high-dimensions, and a parameter $k$, the goal is to preprocess the dataset, such that given a query point $q$, one can compute quickly a point $xinP$, such that the distance of the query to the point $x$ is minimized, when ignoring the "optimal" $k$ coordinates. Note, that the coordinates being ignored are a function of both the query point and the point returned. We present a general reduction from this problem to answering ANN queries, which is similar in spirit to LSH (locality sensitive hashing) [IM98]. Specifically, we give a sampling technique which achieves a bi-criterion approximation for this problem. If the distance to the nearest neighbor after ignoring $k$ coordinates is $r$, the data-structure returns a point that is within a distance of $O(r)$ after ignoring $O(k)$ coordinates. We also present other applications and further extensions and refinements of the above result. The new data-structures are simple and (arguably) elegant, and should be practical -- specifically, all bounds are polynomial in all relevant parameters (including the dimension of the space, and the robustness parameter $k$).

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

Recommendations

• scientific article; zbMATH DE number 1775450
• Approximate line nearest neighbor in high dimensions
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Approximate nearest neighbor queries revisited
• Approximate nearest neighbor search in high dimensions

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Cited In (3)

• Proximity Search with a Triangulated Spatial Model
• Analysis of the Period Recovery Error Bound
• Index structures for fast similarity search for binary vectors

This page was built for publication: Proximity in the age of distraction: robust approximate nearest neighbor search

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