Dec, 2022

高维空间中更快的最大内积搜索

PDF
TL;DR本文提出了一种名为 BanditMIPS 的随机算法，解决了在高纬度情况下复杂度至少为 O (根号 d) 的 MIPS 任务。此算法通过自适应子采样和多臂老虎机策略来估计每个原子的内积，并在理论和实验中都得到了证明。
maximum inner product searchbanditmipsrandomized algorithmhigh-dimensional settingsmulti-armed bandits
发现论文，激发创造
  • 基于贪心算法的有限预算最大内积搜索

    本文研究带有计算开销的 MIPS 问题，通过设计新型的贪心 - MIPS 算法，从而灵活地控制搜索效率与搜索质量的平衡。在半百万个 200 维向量的候选集上，与现有算法相比，贪心 - MIPS 不仅简单易懂，而且速度快且性能好。

    Oct, 2016

  • 一种用于最大内积搜索的贝叶斯赌博算法

    本研究提出了第一种无需任何预处理的近似 MIPS 算法，并允许用户控制和限制结果的次优性，该方法将 MIPS 作为最佳 Arm 识别问题，并引入了一种新的赌博问题设置来充分利用 MIPS 的特殊结构，在合成和现实世界数据集上表现优于现有方法。

    Dec, 2018

  • 基于量化的快速内积搜索

    我们提出了一种基于量化的方法，用于快速近似最大内积搜索（MIPS），该方法利用一组通过最小化内积量化误差直接学习的码书对每个数据库向量在多个子空间上进行量化。通过子空间量化器的内积和来近似查询到数据库向量的内积。与最近提出的 LSH 方法不同，数据库向量和查询不需要在高维特征空间中进行扩展。我们还提供了所提出方法的理论分析，在较温和的假设下得出集中结果。此外，如果在训练时给出少量示例查询，则我们提出了修改的码书学习过程，可以进一步提高准确性。在包括来自深度神经网络的数据集在内的各种数据集上进行的实验结果表明，所提出的方法明显优于现有最先进的方法。

    Sep, 2015

  • 逆向最大内积搜索：如何高效地找到有意购买我的物品的用户？

    本文提出了一种新的问题，称为 “反向最大内积搜索 (RMIPS)”，并通过提出一种名为 Simpfer 的简单、快速和准确的算法来解决，能够在用户向量和项目向量中找到与查询向量最大内积的向量，实验证明其性能优于 MIPS 技术并且更快。

    Oct, 2021

  • 聚类在近似最大内积搜索中效率高

    本文主要探讨了最大内积搜索的效率问题，提出了一种基于 k 均值聚类算法的简单方法，在保证检索准确率的同时显著提高检索速度，并在两个标准推荐系统基准测试和大词汇量词嵌入上进行了实验证明。

    Jul, 2015

  • 针对最大内积搜索（MIPS）的改进非对称局部敏感哈希（ALSH）

    本文提供了一种将最大内积搜索问题转化为余弦相似度搜索问题的方法，该方法使用了不对称变换和有符号随机投影进行优化，相较于之前的方法更为高效。

    Oct, 2014

  • 基于聚类的近似最大内积搜索中的乐观查询路由

    本研究旨在研究基于聚类的最近邻搜索中路由问题，通过乐观主义的原则，利用内积分布的矩来乐观地估计最大内积，通过只使用前两个矩实现与现有算法相当准确度的搜索，并且所提出的算法在空间利用上也更为高效。

    May, 2024

  • 用于亚线性时间最大内积搜索（MIPS）的非对称局部敏感哈希（ALSH）

    本文提出了第一个可证明的次线性时间算法，用于近似最大内积搜索，该建议也是使用未归一化的内积作为底层相似度度量的第一个哈希算法。

    May, 2014

  • SAH: 可感知轮换的非对称哈希用于反向 $k$ 最大内积搜索

    该论文研究了一种名为 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

  • 基于邻近图的最大内积搜索的理解与改进

    分析了最大内积搜索中的范数偏差，证明了 ip-NSW 算法的性能优秀是因为其匹配了最大内积搜索的范数偏差，同时提出了 ip-NSW + 算法，通过引入角度相似性图表现出更好的性能表现。

    Sep, 2019