A Note on Approximate Nearest Neighbor Methods

2007/03/21 by Breuel, Thomas M.
#Computational Complexity (cs.CC) #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Information Retrieval (cs.IR)

paper · doi:10.48550/arxiv.cs/0703101

Abstract

A number of authors have described randomized algorithms for solving the epsilon-approximate nearest neighbor problem. In this note I point out that the epsilon-approximate nearest neighbor property often fails to be a useful approximation property, since epsilon-approximate solutions fail to satisfy the necessary preconditions for using nearest neighbors for classification and related tasks.

Related

• Approximate Nearest Neighbor Search in High Dimensions
• K-Nearest Neighbor Approximation Via the Friend-of-a-Friend Principle
• A Sub-linear Time Algorithm for Approximating k-Nearest-Neighbor with Full Quality Guarantee
• Rates of Convergence for Nearest Neighbor Classification
• Approximate nearest neighbor search for ℓ_p-spaces (2 < p < ∞) via embeddings