Charles
数据结构
Multi-Probe LSH 是原生局部敏感哈希（LSH）的工业级优化算法，核心解决了原生LSH“召回率不足、堆表内存开销巨大”的核心痛点。作为哈希派系ANN近似检索的进阶方案，它无需暴力搭建大量哈希表，仅通过智能探测邻近桶，就能在极低内存开销下大幅提升检索召回率，是高维向量检索场景的经典优化方案。原生LSH存在天然短板，其依靠概率哈希映射让相似向量落入同一桶，仅能保证大概率同桶，而非百分百。这就导致部分邻近向量会被划分至相邻桶，造成漏检、召回率偏低。为弥补这一缺陷，传统工程方案只能堆叠10至20组哈希表，通过多组哈希函数交叉检索提升召回率，但直接造成内存开销成倍暴涨，海量数据场景下落地成本极高，这也是原生LSH难以大规模商用的核心矛盾。2007年VLDB会议提出的Multi-Probe LSH彻底破解了这一困境，其核心思想十分直观：不再暴力堆砌哈希表，而是对单张哈希表，智能探测查询桶周边的邻近桶。基于LSH的映射特性，被漏检的邻近向量，大概率分布在查询向量所在桶的相邻区域，探测邻近桶即可高效找回漏检样本。该算法通过扰动向量实现邻近桶定位。原生LSH的哈希值为多维向量，Multi-Probe LSH通过生成由-1、0、+1组成的扰动向量，对原始哈希值进行微调：0代表保留原桶，±1代表探测左右相邻桶。这种微调无需重新计算向量哈希，计算开销极低，兼顾效率与精准度。为避免盲目探测，算法采用步进式探寻+查询导向排序的核心创新。按照扰动非零元素数量划分探测步数，从0步原桶、1步近邻桶到2步次近邻桶，由近及远逐层探测。同时依据查询点到桶边界的距离打分排序，查询点越靠近某侧边界，该方向邻近桶漏检概率越高，优先探测对应桶，以最少探测次数实现最高召回率。工程上可通过最小堆算法高效生成最优扰动序列，进一步提升检索效率。在工作流程上，Multi-Probe LSH的索引构建与原生LSH完全一致，无需额外改造，仅在检索阶段增加多桶探测逻辑，工程改造成本极低。检索时先计算查询向量哈希值与边界距离，生成有序扰动序列，逐层探测邻近桶，最后对所有候选向量精准排序，输出Top-K近邻结果。相比原生LSH，其核心优势十分突出：同等召回率下，哈希表数量可减少一个数量级，内存开销大幅降低；通过精准邻近探测有效减少漏检，召回率显著提升
发布于 江苏
分享
评论
4
未登录
友善发言
评论
加载中
