Approximate nearest neighbor search for ℓ_p-spaces (2 < p < ∞) via embeddings

2015/12/06 by Yair Bartal, Bartal, Yair, Lee-Ad Gottlieb +1
Computer Science · Engineering · Mathematics · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Mathematical Approximation and Integration #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1512.01775

openalex publication_date 2015/12/06 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and ℓ₁, few non-trivial algorithms are known for ℓ_p when (2 &lt; p &lt; ∞). In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the first non-trivial approximation factor guarantees in this setting.

Related

• Approximate Nearest Neighbor Search for Low Dimensional Queries
• Approximate Nearest Neighbor Search in High Dimensions
• Approximate Nearest Neighbors in Limited Space
• Approximate Nearest Neighbor Search in ℓ_p
• Hardness of Approximate Nearest Neighbor Search under L-infinity