局部敏感哈希(LSH)

定义

局部敏感哈希(Locality-Sensitive Hashing,LSH)由 Piotr Indyk 与 Rajeev Motwani 等人提出,指一族特殊哈希函数:相似的输入以高概率映射到同一哈希桶,不相似的输入以高概率分开,从而把近邻搜索转化为桶内查找。

原理

针对不同相似度度量有不同的 LSH 函数族:Jaccard 相似度对应 MinHash,余弦相似度对应随机超平面投影,欧氏距离对应 p-稳定分布投影。工程上通过"多个哈希函数级联成一个桶键、再建多张哈希表"的方式在查全率与查准率之间权衡。

应用

LSH 用于网页与图片去重、指纹音频识别、海量向量的近似最近邻检索,是向量索引出现之前的主流方案。

优缺点

优点是有概率理论保证、支持流式插入;缺点是内存开销大、参数调优复杂,在高召回要求下常不如 HNSW 等图索引高效。