跳转到内容
Jason's Study

LSH — 让相似点撞同一个桶，把高维最近邻查询从线性变成亚线性

是什么

LSH（Locality-Sensitive Hashing，局部敏感哈希）是一套让”靠得近的点”大概率撞进同一个哈希桶、“离得远的点”大概率分开的设计方法。

日常类比：普通哈希函数（比如 MD5）追求”输入差一个字符也要看起来完全不同”——这对查重是好事，对查相似就是灾难。LSH 反过来：故意让相近的输入撞车，于是只要看哪些东西和你撞同一个桶，就能在一堆候选里飞快地挑出最近的邻居。

经典场景：你有 1 亿张图片向量（每张 512 维），来一个查询向量 q，要找”和 q 最像的那张”。

  • 朴素做法：和每张算一遍距离 → 1 亿次乘法
  • LSH：把所有向量预先哈希进若干张桶表，q 来了只哈希一次，扫一两个桶里的候选 → 亚线性时间

为什么重要

不理解 LSH，下面这些事都没法解释：

  • 为什么 1998 年之前大家都觉得”高维最近邻只能线性扫”，之后突然有了向量数据库这个赛道
  • 为什么 Faiss / Pinecone / Milvus 这些向量库的论文反复提到 ρ（rho）这个数
  • 为什么 AltaVista / Google 早年能在 PB 级网页里秒级查重——MinHash 是 LSH 的特例
  • 为什么深度学习时代的 embedding 搜索没有从零设计算法——直接接上 1998 年的理论楼梯

核心要点

LSH 的设计可以拆成 三步：

  1. 定义”敏感”哈希族：找一族哈希函数 h，使得”近的点撞车概率 ≥ p1，远的点撞车概率 ≤ p2”，且 p1 > p2。这族函数叫 (r1, r2, p1, p2)-sensitive。

  2. 拼接放大差距（k 个哈希连成一个）：单个 h 区分能力不够，把 k 个 h 连成 g = (h1, …, hk)。p1^k 和 p2^k 的差距被指数放大——近的还是大概率撞，远的几乎一定不撞。

  3. 多张表保召回（L 张独立哈希表）：单张表运气不好可能漏掉真正的最近邻。用 L 张独立的 g 各建一张表，“至少有一张撞上”的概率被指数推高。

复杂度的核心是一个数：ρ = log(1/p1) / log(1/p2)。 查询时间是 O(n^ρ · d)，空间 O(n^(1+ρ))。Hamming 距离下 ρ = 1/c（c 是允许的近似倍数）。c = 2 就是 ρ = 0.5，n = 10^8 时只看约 10^4 个候选。

实践案例

案例 1：Hamming 距离的 LSH——比特采样

设两条 64 位指纹，距离用”不同位数”算。

  • 哈希函数：随机挑一个位，h(p) = p 的第 i 位
  • 两条指纹差 d 位 → 撞车概率 = (64 − d) / 64

差 1 位 → 撞车概率 63/64；差 32 位 → 撞车概率 1/2。完美的”近的撞、远的散”。

把 k 个比特位拼起来作为 g，再开 L 张表，复杂度立刻变成 n^(1/c) 量级。这就是 1998 论文里的核心定理。

案例 2：MinHash —— 集合 Jaccard 相似度的 LSH

Broder 1997 在 AltaVista 用过。把每个网页变成一个”词集合”，问题是”两个集合 Jaccard 相似度多少”。

  • 把所有词随机置换成新顺序
  • 取每个集合在新顺序里”最小的那个词”作为哈希值
  • 数学事实：Pr[MinHash(A) = MinHash(B)] = |A ∩ B| / |A ∪ B|（恰好等于 Jaccard）

这就是 LSH 框架下的一个具体族。AltaVista 用它做网页去重，Google 早期 sitemap 也借鉴。

案例 3：欧氏距离的 LSH（Datar 2004 后续）

原 1998 论文是 Hamming，后来 Datar 等人补了 L2：

  • 取一个随机方向 a（高斯随机向量）+ 随机偏移 b
  • h(p) = floor((a · p + b) / w)，w 是桶宽

直觉：把空间随机投影到一条线上，按等长区间切片。近的点投到同一片的概率高。这是现代 Faiss 里 LSH 索引的原型。

案例 4：把 1 亿 embedding 装进单机的工程账

假设 n = 1e8，d = 768（BERT-base 维度），c = 2 → ρ = 0.5。

  • 单查询候选数 ≈ n^ρ = 1e4
  • 单查询距离计算 ≈ 1e4 × 768 ≈ 7.7M FLOPs，毫秒级
  • 表数 L ≈ n^ρ ≈ 1e4，桶 key 是 k 个比特位的拼接，单表内存约 1e8 × 32B = 3.2GB，L 张就 32TB——不现实

所以工程上 L 取小（几十张）+ 牺牲一点召回；或换成 IVF（聚类版 LSH）压空间。这就是 1998 理论值和 Faiss 实战参数差好几个数量级的原因。

踩过的坑

  1. k 和 L 怎么调是手艺活：k 大 → 远的更难撞但近的也开始漏；L 大 → 召回上去但内存和查询时间也上去。论文给了理论最优 k = log(n) / log(1/p2)，但实践常常需要试。

  2. 近似因子 c 影响 ρ 是指数级：要”严格找最近”（c → 1）会让 ρ → 1，退化成线性扫。LSH 本质是用近似换速度，不能强求精确。

  3. 冷桶问题：稀有点会被分到很大的桶里，查询时该桶要扫一长串。生产系统要加桶大小上限或多探测（multi-probe LSH）。

  4. 现代 HNSW 在实际数据上常打过原始 LSH：图索引（HNSW、NSG）利用了”真实数据低维流形”这个先验，在 ANN benchmark 上经常更快。但理论上界仍然是 LSH 给的——HNSW 没有亚线性的最坏情况证明。

  5. 空间放大不能忽视：n^(1+ρ) 看着小，n=10^8、ρ=0.5 就是 10^12 级桶项。生产里通常压缩成位图或 Bloom 过滤。

适用 vs 不适用场景

适用：

  • 高维（d > 100）、海量（n > 10^6）、对精度可妥协的最近邻查询
  • 需要最坏情况亚线性保证的场景（计费搜索 / 安全审计）
  • 流式去重、网页查重（MinHash）
  • 作为粗排候选生成 → 再用精确距离重排
  • 教学场景：理解”近似算法 + 概率分析”组合拳的最好入门样本

不适用：

  • 低维（d < 20）小数据 → 直接 kd-tree / 暴力扫更快更准
  • 要求 100% 精确最近邻 → LSH 是近似算法
  • 数据有明显流形结构、查询可以学 → HNSW / IVF-PQ 实测更优
  • 在线频繁插入删除 → 多张哈希表维护成本不低
  • GPU 全量点积已能接受时（向量量小、d 小、用 A100/H100）→ 暴力反而最快

历史小故事（可跳过）

  • 1997 年：Andrei Broder 在 AltaVista 做网页去重，发明 MinHash。当时还没”LSH”这个词，论文里就叫”shingling + min-wise permutation”。
  • 1998 年：Indyk（当时在 Stanford 读博）和导师 Motwani 把 MinHash 这类构造抽象成统一框架——“局部敏感哈希族”，给出第一份亚线性查询 + 多项式空间的可证明上界。这就是 STOC 1998 这篇 12 页论文。
  • 1999 年：Gionis-Indyk-Motwani 在 VLDB 发了工程化版本，开始有真实系统采用。
  • 2004 年：Datar 等人补上 L2 距离的 p-stable LSH，向量搜索时代开始。
  • 2014 年后：ANN benchmarks 把 LSH、HNSW、IVF 拉一起 PK——LSH 仍是理论压舱石，但工程榜常被图索引压一头。
  • 2020 年代：大模型时代每条 prompt 都要查相似 embedding，LSH 类思想又借 RAG 回到一线——理论扎实的算法不会真的过时。

学到什么

  1. “故意制造碰撞”也是设计——传统哈希追求散列均匀，LSH 反着来。需求决定算法，不是反过来
  2. 拼接 + 多表 = 指数放大差距：单个弱信号无用，组合后变强信号。这个套路在概率算法里反复出现（Bloom 过滤、Count-Min、各种 sketch）
  3. 近似换速度：精确 NN 在高维要 Ω(n)，放宽一点（c-近似）就能 n^ρ。这种”放一寸要一里”的妥协是算法设计核心思路
  4. 理论 → 工程隔了 6 年（1998 → 2004 真正能跑欧氏距离）。基础研究的回报曲线很长
  5. 维度灾难不是不可逾越：1998 之前学界普遍接受”高维 NN 必然线性”，LSH 用一个简单的概率构造把这堵墙凿了个洞。新人写论文常常被”大家都说不行”吓退，但有时只是没人敢动手

延伸阅读

关联

  • ance-2020 —— ANCE 等稠密检索方法生成 embedding，再用 LSH/HNSW 做最近邻
  • consistent-hashing-1997 —— 同年代另一个”工程定义哈希家族”的代表，但目标是负载均衡而非相似搜索
  • anserini-2017 —— 文本检索的另一极：稀疏（BM25）vs 稠密（embedding + LSH）
  • cook-levin —— LSH 之所以”近似”，是因为精确高维 NN 接近 NP-hard 边界
  • karp-21 —— 同样是”近似换可解性”思路在 NP-hard 问题上的体现，思想一脉相承

反向链接

  • anserini-2017 —— Anserini — 把工业搜索引擎 Lucene 改造成学术 IR 实验台
  • consistent-hashing-1997 —— Consistent Hashing — 加机器只搬一小部分数据的哈希环
  • cook-levin —— Cook-Levin 定理 — NP-完全性的诞生
  • karp-21 —— Karp 21 — 21 个 NP-完全问题
  • minhash-broder-1997 —— MinHash — 用最小哈希值估算两个集合的重叠度
  • simhash-charikar-2002 —— SimHash — 用随机超平面把余弦相似度变成汉明距离