A randomized approximate nearest neighbors algorithm

DOI10.1016/J.ACHA.2012.07.003MaRDI QIDQ1948601zbMATH OpenOpenAlexFDO

Authors Peter Jones, Andrei Osipov, Vladimir Rokhlin

Publication date 24 April 2013

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.acha.2012.07.003

zbMATH Keywords

approximate nearest neighborsfast random rotationsrandomized algorithms

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• scientific article; zbMATH DE number 437552
• Exact \(L_{\infty}\) nearest neighbor search in high dimensions
• scientific article; zbMATH DE number 1559575
• scientific article; zbMATH DE number 1775450
• Approximate nearest neighbor queries revisited

Cited in

(14)

• Probabilistic analysis of an algorithm for solving the \(k\)-dimensional all-nearest-neighbors problem by projection
• Analysis of an adaptive algorithm to find the two nearest neighbors
• Graph-theoretic algorithms for Kolmogorov operators: approximating solutions and their gradients in elliptic and parabolic problems on manifolds
• Random-walk based approximate \(k\)-nearest neighbors algorithm for diffusion state distance
• Spatiotemporal pattern extraction by spectral analysis of vector-valued observables
• A class of Laplacian multiwavelets bases for high-dimensional data
• ASKIT: an efficient, parallel library for high-dimensional kernel summations
• Approximate nearest neighbors and sequence comparison with block operations
• Detecting low-rank clusters via random sampling
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Fast cross-polytope locality-sensitive hashing
• scientific article; zbMATH DE number 1830741 (Why is no real title available?)
• Nearest neighbor sampling of point sets using rays
• Index structures for fast similarity search for real vectors. II

This page was built for publication: A randomized approximate nearest neighbors algorithm

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