第 111 题：近似最近邻(ANN)的LSH，局部敏感哈希族的构造？
题目
近似最近邻(ANN)的LSH，局部敏感哈希族的构造？
完整讲解
一、近似最近邻（ANN）与 LSH
精确最近邻在大规模高维下成本高（暴力 $O(Nd)$），ANN 用索引与近似算法在召回率与延迟间折中。局部敏感哈希（LSH）：若两点相似（距离小），则它们以高概率落入同一桶；若不相似，则以高概率落入不同桶。通过多组哈希函数与多桶，可放大「相似→同桶」的概率，实现快速候选筛选。
二、LSH 族的定义
哈希族 $\mathcal{H}$ 称为对距离 $D$ $(r, cr, p_1, p_2)$-敏感的，若：距离 $\le r$ 的点对以概率 $\ge p_1$ 发生碰撞；距离 $\ge cr$ 的点对以概率 $\le p_2$ 发生碰撞；且 $p_1 > p_2$、$c>1$。好的 LSH 族要求 $p_1$ 尽量大、$p_2$ 尽量小，使真近邻易同桶、远点易分离。
三、常见 LSH 族的构造
- 欧氏距离（L2）：p-stable LSH。利用 p-stable 分布（如 $p=2$ 对应高斯）：$h_{\boldsymbol{a},b}(\boldsymbol{x}) = \lfloor \frac{\boldsymbol{a}^\top \boldsymbol{x} + b}{w} \rfloor$，其中 $\boldsymbol{a}$ 服从高斯、$b \sim U(0,w)$。距离近的 $\boldsymbol{x}$ 在 $\boldsymbol{a}^\top \boldsymbol{x}$ 上接近，易落入同一整数桶。
- 余弦相似度 / 内积：随机投影。$h(\boldsymbol{x}) = \text{sign}(\boldsymbol{a}^\top \boldsymbol{x})$，$\boldsymbol{a}$ 为单位随机向量。内积大则 $\boldsymbol{a}^\top \boldsymbol{x}$ 同号概率大，可做 SimHash；或多 bit 扩展为多桶。
- 汉明距离：位采样或 MinHash（用于集合 Jaccard）。对 0/1 向量，LSH 可直接用子位或 MinHash 族。
四、多表与多哈希
单次哈希碰撞率有限，通常建 $L$ 张表、每表用 $k$ 个哈希函数组合成复合桶（$g=(h_1,\ldots,h_k)$）。查询时对 $q$ 算 $g(q)$，在 $L$ 个桶内取并集作候选。$L$、$k$ 增大则召回升、延迟与存储也升，需按 recall/latency 调参。
面试要点
- 能说明 LSH 的直观：相似点高概率同桶、不相似高概率不同桶；$(r, cr, p_1, p_2)$ 定义。
- 能写出欧氏下的 p-stable（$h = \lfloor (\boldsymbol{a}^\top \boldsymbol{x}+b)/w \rfloor$）与内积/余弦下的 sign 随机投影。
- 能说清多表 $L$、每表 $k$ 个哈希对召回与延迟的权衡。
记忆要点
- LSH：相似→高概率同桶；需 $p_1>p_2$。欧氏用 p-stable；内积/余弦用 sign 随机投影。
- 多表 $L$、复合 $g=(h_1,\ldots,h_k)$ 提高召回；$L,k$ 大则延迟与存储增。
- 调参：$w$、$L$、$k$ 根据 recall/latency 曲线选。