Locality-sensitive Hashing

释义 Definition

局部敏感哈希（LSH）：一种用于近似最近邻搜索与相似度检索的哈希方法。它把“相似”的高维数据（如文本向量、图像特征）以较高概率映射到同一哈希桶，从而在海量数据中更快地找到相似对象（常用于降维后仍很昂贵的检索场景）。该术语也常泛指一类“对距离/相似度敏感”的哈希函数族。（在不同文献中会针对不同距离度量如余弦相似度、Jaccard、欧氏距离而有不同LSH方案。）

发音 Pronunciation (IPA)

/loʊˈkælɪti ˈsɛnsɪtɪv ˈhæʃɪŋ/

例句 Examples

We use locality-sensitive hashing to quickly find similar documents.
我们使用局部敏感哈希来快速找到相似的文档。

In large-scale image search, locality-sensitive hashing reduces the need to compare every feature vector by grouping likely neighbors into the same buckets.
在大规模图像检索中，局部敏感哈希通过把可能相近的向量分到同一桶里，减少了逐一比较所有特征向量的需求。

词源 Etymology

该术语由三部分构成：locality（局部性/邻近性）+ sensitive（敏感的）+ hashing（哈希）。其核心思想是让哈希函数对“邻近（相似）关系”保持敏感：距离更近/更相似的数据更容易碰撞到同一哈希值或同一桶中。作为计算机科学术语，它在近似最近邻（ANN）研究中被系统化提出并广泛传播。

相关词 Related Words

• Approximate
• Nearest Neighbor
• Similarity
• Jaccard
• Cosine Similarity
• Minhash
• Hash Function
• Clustering
• Dimensionality Reduction

文献与作品 Literary / Notable Works

• Indyk & Motwani (1998), Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality（提出并奠定LSH框架的经典论文）
• Andoni & Indyk (2006), Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions（LSH理论与改进的重要工作）
• Rajaraman, Leskovec & Ullman, Mining of Massive Datasets（大规模数据挖掘教材中常用LSH讲解相似文档/集合检索）
• Manning, Raghavan & Schütze, Introduction to Information Retrieval（信息检索教材中涉及近似相似检索相关方法，常与LSH并读）