Approximate Nearest Neighbor

定义 Definition

Approximate Nearest Neighbor（近似最近邻，常缩写为 ANN）：在给定查询点（或向量）时，不要求找到“绝对最近”的那个邻居，而是用更快的算法找到足够接近最近邻的结果，用速度、内存或可扩展性换取少量精度损失。常用于高维向量检索、推荐系统、图像/文本相似度搜索与向量数据库。

发音 Pronunciation (IPA)

/əˈprɑːksɪmət ˈnɪərɪst ˈneɪbər/

例句 Examples

Approximate nearest neighbor search can return results in milliseconds.
近似最近邻搜索可以在毫秒级返回结果。

In high-dimensional embedding spaces, approximate nearest neighbor methods are often preferred because exact search becomes too slow as the dataset grows.
在高维嵌入向量空间中，随着数据集增大，精确搜索会变得过慢，因此人们常更偏好使用近似最近邻方法。

词源 Etymology

这是一个组合术语：

• approximate 来自拉丁语 approximare，表示“使接近、近似”。
• nearest neighbor 直译为“最近的邻居”，在数学与计算机科学中指距离度量下最接近的样本点。
  合起来强调：目标是“找最近”，但允许“近似”，以获得更高效率。（该术语也常泛指一类相似度检索算法与问题设定。）

相关词 Related Words

• Nearest Neighbor
• K-Nearest Neighbors
• Similarity Search
• Vector Database
• Locality-Sensitive Hashing
• HNSW
• KD-Tree
• Embedding
• Cosine Similarity

文献与著作中的出现 Literary / Notable Works

• Indyk & Motwani（1998）Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality（经典论文，奠定 ANN 问题与方法框架）
• Andoni & Indyk（2008）Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions（高维 ANN 与哈希方法的重要研究）
• Malkov & Yashunin（2018）Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs（HNSW 方法的代表性论文）
• Manning, Raghavan & Schütze（Introduction to Information Retrieval）信息检索经典教材中讨论相似检索与近似方法
• Leskovec, Rajaraman & Ullman（Mining of Massive Datasets）大规模数据处理中涉及近似检索/相似搜索的相关内容