本文提出了第一个可证明的次线性时间算法,用于近似最大内积搜索,该建议也是使用未归一化的内积作为底层相似度度量的第一个哈希算法。
May, 2014
该论文研究了一种名为 Reverse k-Maximum Inner Product Search (RkMIPS) 的新问题,并提出了一种名为 Shifting-aware Asymmetric Hashing (SAH) 的子二次时间算法来解决该问题。该算法基于一种不变的不对称变换,设计了 Shifting-Aware Asymmetric Locality Sensitive Hashing (SA-ALSH) 方案以加速 item vectors 上的 Maximum Inner Product Search (MIPS),并使用基于 Cone-Tree 的新型阻塞策略来批量有效地修剪用户向量。在 5 个真实世界的数据集上进行实验,证明 SAH 比现有的 RkMIPS 方法快 4 到 8 倍,同时实现了超过 90%的 F1-score。
Nov, 2022
本文主要探讨了最大内积搜索的效率问题,提出了一种基于 k 均值聚类算法的简单方法,在保证检索准确率的同时显著提高检索速度,并在两个标准推荐系统基准测试和大词汇量词嵌入上进行了实验证明。
Jul, 2015
该论文系统研究了内积相似性连接问题,提出了新的上下界和基于线性草图的索引方法,并探讨了不对称性的影响。
Oct, 2015
研究局部敏感哈希的设计问题中对内积相似度问题的对称和非对称哈希的功效及提供了性能更好的对称 LSH 解决方案和非对称 LSH 的变体的需求场景。
Oct, 2014
本研究提出了第一种无需任何预处理的近似 MIPS 算法,并允许用户控制和限制结果的次优性,该方法将 MIPS 作为最佳 Arm 识别问题,并引入了一种新的赌博问题设置来充分利用 MIPS 的特殊结构,在合成和现实世界数据集上表现优于现有方法。
Dec, 2018
本文提出了一种名为 BanditMIPS 的随机算法,解决了在高纬度情况下复杂度至少为 O (根号 d) 的 MIPS 任务。此算法通过自适应子采样和多臂老虎机策略来估计每个原子的内积,并在理论和实验中都得到了证明。
Dec, 2022
该研究提出了 Norm-ranging LSH 的哈希方法,它可以通过将数据集划分为多个子数据集,为每个子数据集建立一个哈希索引,改善 Simple-LSH 中长尾规范化问题,并且证明 Norm-ranging LSH 具有比 Simple-LSH 更低的查询时间复杂度。此外,该研究还提出了一种新的相似度度量方法。实验证明,相对于 Simple-LSH,Norm-ranging LSH 可以实现一个数量级的加速,并显著提高了涉及最大内积搜索的应用程序性能。
Sep, 2018
本研究旨在研究基于聚类的最近邻搜索中路由问题,通过乐观主义的原则,利用内积分布的矩来乐观地估计最大内积,通过只使用前两个矩实现与现有算法相当准确度的搜索,并且所提出的算法在空间利用上也更为高效。
May, 2024
本文研究带有计算开销的 MIPS 问题,通过设计新型的贪心 - MIPS 算法,从而灵活地控制搜索效率与搜索质量的平衡。在半百万个 200 维向量的候选集上,与现有算法相比,贪心 - MIPS 不仅简单易懂,而且速度快且性能好。
Oct, 2016