Oct, 2015

内积相似性连接的复杂性

PDF
TL;DR该论文系统研究了内积相似性连接问题，提出了新的上下界和基于线性草图的索引方法，并探讨了不对称性的影响。
inner product similarity joinasymmetric locality-sensitive hashinglinear sketchesvector normalizationalgorithm analysis
发现论文，激发创造
  • 针对最大内积搜索（MIPS）的改进非对称局部敏感哈希（ALSH）

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

    Oct, 2014

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

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

    May, 2014

  • 对称和非对称 LSH 用于内积搜索

    研究局部敏感哈希的设计问题中对内积相似度问题的对称和非对称哈希的功效及提供了性能更好的对称 LSH 解决方案和非对称 LSH 的变体的需求场景。

    Oct, 2014

  • 关于神经网络图嵌入的表示能力及其拓展

    本文提出了一种名为 SIPS 的新模型，通过在 Minkowski 空间内考虑内积，SIPS 能够很好地逼近各种条件正定的相似度，从而从理论上得出 SIPS 优于 IPS 的结论。

    May, 2018

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

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

    Jul, 2015

  • 加权内积表示学习实现通用相似度近似

    本文提出一种基于神经网络的图嵌入方法 —— 加权内积相似性，其能够优化相似度模型，学习任何相似度模型，且在节点表示学习和归纳任务中有高效表现。

    Feb, 2019

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

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

    Sep, 2015

  • 范数范围局部敏感哈希用于最大内积搜索

    该研究提出了 Norm-ranging LSH 的哈希方法，它可以通过将数据集划分为多个子数据集，为每个子数据集建立一个哈希索引，改善 Simple-LSH 中长尾规范化问题，并且证明 Norm-ranging LSH 具有比 Simple-LSH 更低的查询时间复杂度。此外，该研究还提出了一种新的相似度度量方法。实验证明，相对于 Simple-LSH，Norm-ranging LSH 可以实现一个数量级的加速，并显著提高了涉及最大内积搜索的应用程序性能。

    Sep, 2018

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

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

    Sep, 2019

  • 使用树形数据结构进行最大内积搜索

    本文提出了针对内积最优匹配问题的新型分支边界算法，包括使用树形结构的一般分支边界算法、针对多个查询的双树算法以及新型数据结构等，实验结果表明与朴素搜索技术相比，该算法能使查询时间提升高达 5 个数量级。

    Feb, 2012