基于聚类的近似最大内积搜索中的乐观查询路由
内容提要
本文探讨了最大内积搜索（MIPS）的效率问题，提出了基于聚类和量化的多种方法，以提高检索速度和准确性。研究表明，新算法在多个数据集上优于现有技术，尤其在高维情况下，能够有效平衡搜索效率与质量。
延伸解读
从预处理到免预处理：MIPS 算法的演进
文章梳理了近似最大内积搜索（MIPS）算法的演进脉络。早期方法如基于 k 均值聚类和不对称变换，通常需要预处理或依赖特定变换。2018 年提出的方法首次实现无需预处理的近似 MIPS，并允许用户控制结果的次优性，这降低了使用门槛。2022 年的 BanditMIPS 则利用多臂老虎机策略，在高维下达到 O(√d) 复杂度，进一步提升了效率。这些进展显示 MIPS 研究正朝着更实用、更灵活的方向发展。
量化与哈希：两条高效检索路径
文章介绍了基于量化和哈希的两类高效 MIPS 方法。量化方法通过最小化内积量化误差学习码书，在多个子空间上量化数据库向量，并用内积和近似查询结果，避免了高维特征扩展。哈希方法则包括有符号随机投影和 SAH 算法，后者针对反向 k-MIPS 问题，结合不对称变换和 Cone-Tree 阻塞策略，在真实数据集上比现有方法快 4 到 8 倍，F1-score 超过 90%。这两条路径各有侧重，为不同场景提供了选择。
反向 MIPS：新兴问题与算法突破
文章特别关注了反向最大内积搜索（RMIPS）这一新问题。与给定查询找最相似项的传统 MIPS 不同，RMIPS 旨在找到与查询向量内积最大的用户向量。2021 年提出的 Simpfer 算法简单快速，性能优于传统 MIPS 技术。2022 年的 SAH 算法进一步解决了反向 k-MIPS 问题，在 5 个真实数据集上实现了 4 到 8 倍的加速。这些工作表明，反向 MIPS 正成为检索领域的重要分支，尤其适用于推荐和搜索场景。
范数偏差与算法设计启示
文章分析了最大内积搜索中的范数偏差问题，指出 ip-NSW 算法的优秀性能源于其匹配了 MIPS 的范数偏差。基于此，研究者提出了 ip-NSW+ 算法，通过引入角度相似性图进一步提升了性能。这一发现提示，在设计 MIPS 算法时，考虑数据范数分布和相似性度量的匹配至关重要。忽略范数偏差可能导致检索质量下降，而针对性地调整图结构或哈希函数则能带来显著改进。
Q&A
最大内积搜索（MIPS）是什么？
最大内积搜索（MIPS）是一种用于在高维空间中寻找与查询向量具有最大内积的数据库向量的技术。
如何提高最大内积搜索的效率？
可以通过基于聚类和量化的方法、贪心算法以及不对称变换等技术来提高最大内积搜索的效率。
BanditMIPS算法的特点是什么？
BanditMIPS算法通过自适应子采样和多臂老虎机策略，解决高维情况下复杂度为O(根号d)的MIPS任务，具有较高的效率。
反向最大内积搜索（RMIPS）有什么创新？
反向最大内积搜索（RMIPS）提出了一种名为Simpfer的算法，能够更快地找到与查询向量最大内积的向量，性能优于传统MIPS技术。
如何将最大内积搜索转化为余弦相似度搜索？
通过使用不对称变换和有符号随机投影的方法，可以将最大内积搜索问题转化为余弦相似度搜索问题，从而提高效率。
ip-NSW + 算法的优势是什么？
ip-NSW + 算法通过引入角度相似性图，能够更好地匹配最大内积搜索中的范数偏差，从而表现出更好的性能。
