算法概述：LSH

局部敏感哈希（LSH）是一种近似最近邻（ANN）算法，用于高效地在高维数据中进行相似性搜索。其他ANN方法，例如HNSW，采用基于图的结构，而IVF则采用以聚类为中心的方法，LSH通过利用一组专门的哈希函数而独树一帜。这些函数以概率方式将相似向量分组。其基本思想很巧妙：如果两个向量在高维空间中接近，一个选取得当的哈希函数应该以更高的概率将它们分配到相同的哈希码（或“桶”）中，而不是分配给两个相距较远的向量。

核心思想：将相似项目哈希到一起

设想你有一个庞大的图书馆，但没有完美的目录，而是有几个近似的分类系统。一个系统可能按作者姓氏的首字母对图书进行分组，另一个按封面的主要颜色，还有一个按出版年代。这些系统都不能完美地查找主题完全相同的图书，但如果你向所有系统查询符合你的目标图书特点（作者姓氏首字母为“T”，蓝色封面，1990年代出版）的图书，你就能大大缩小搜索范围。

LSH的工作方式与此类似。它不保证绝对最近邻与查询向量在同一个哈希桶中，但使其可能性很高。为增加这种可能性，LSH通常使用多个哈希表，每个表都用来自同一个LSH族的不同哈希函数构建。

LSH的工作方式

1. 散列：根据使用的距离度量（例如，用于余弦相似度或欧几里得距离的随机投影，用于Jaccard相似度的最小哈希）选择合适的LSH族。从该族生成多个哈希函数。对于数据集中的每个向量，使用这些函数计算其哈希码。通常，多个哈希函数会结合起来为每个哈希表创建一个单一的哈希签名。
2. 索引：将每个向量存储在一个哈希表中，将其放入对应计算哈希码的桶中。由于相似项目之间预期且需要冲突（多个向量落在同一个桶中），因此桶通常存储向量标识符列表。如前所述，通常会使用不同的哈希函数集创建多个独立的哈希表，以增加找到真实邻居的机会。
3. 查询：当查询向量到来时，使用与索引相同的哈希函数计算其哈希码。从所有哈希表中检索存储在相应桶中的所有向量。这个向量集合构成候选集。
4. 细化：由于哈希是近似的，候选集可能包含不是真实近邻的向量（假阳性）。在查询向量和候选集中的所有向量之间执行精确的距离计算。根据它们的真实距离对这些候选者进行排序，并返回前k个结果。

相似的输入向量（如V1、V2和V3、V4）可能会冲突并落入同一个哈希桶。查询Q可能会哈希到一个或多个桶，从而检索候选者（V1、V2、V3、V4）以进行精确比较。

LSH族

LSH的有效性在很大程度上取决于选择适合所用距离度量的LSH族。一些常见例子包括：

• 随机投影：该族常用于近似计算余弦相似度或欧几里得距离。其核心思想涉及生成随机超平面（由随机向量定义）。向量的哈希值由其落在哪一侧的超平面决定。如果两个向量接近（对于余弦相似度，它们之间的夹角小；对于欧几里得距离，距离小），它们很可能落在大多数随机超平面的同一侧，从而得到相似的哈希码。
• 最小哈希：主要为Jaccard相似度设计，它测量集合之间的相似度（常用于表示为n-gram或词语集合的文本文档）。最小哈希使用项目的随机排列，并根据排列后观察到的最小项目ID来哈希集合。Jaccard相似度高的集合更可能产生相同的最小哈希值。

参数与权衡

调整LSH涉及平衡查找邻居的概率与计算成本。重要参数包括：

• 哈希表的数量（$L$）：使用更多哈希表会增加查询向量及其真实邻居至少在一个表中冲突的可能性，从而提高召回率。然而，这也会增加内存使用和查询时间，因为需要检查更多桶。
• 每个表的哈希函数数量（$k$）：每个表使用更多哈希函数会创建更具体的哈希签名（更长的哈希码）。这会减少桶的平均大小，加快候选细化步骤，但也会降低任何单个表的冲突概率。在$L$和$k$之间找到合适的平衡对于优化召回率-速度权衡是十分重要的。

与HNSW等方法相比，LSH有时更难在不同数据集上调整以获得最佳性能。其性能对LSH族和参数（$L$，$k$）的选择敏感。尽管理论上有吸引力，但基于图或基于量化的方法通常在许多常见的向量搜索任务中取得更好的实际结果，特别是在需要高召回率和低延迟时。然而，LSH仍然是一种基本的ANN技术，在重复检测或处理某些类型的数据（如使用最小哈希的集合）等特定方面尤为适用。

了解LSH有助于理解近似搜索的概率性，以及在高维空间中应对最近邻问题的多种可用策略。