A randomized approximate nearest neighbors algorithm

DOI10.1016/J.ACHA.2012.07.003MaRDI QIDQ1948601zbMATHOpenAlexFDO

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

randomized algorithmsapproximate nearest neighborsfast random rotations

Mathematics Subject Classification ID

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

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

(13)

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

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)