NIPSSep, 2018

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

PDF
TL;DR该研究提出了 Norm-ranging LSH 的哈希方法，它可以通过将数据集划分为多个子数据集，为每个子数据集建立一个哈希索引，改善 Simple-LSH 中长尾规范化问题，并且证明 Norm-ranging LSH 具有比 Simple-LSH 更低的查询时间复杂度。此外，该研究还提出了一种新的相似度度量方法。实验证明，相对于 Simple-LSH，Norm-ranging LSH 可以实现一个数量级的加速，并显著提高了涉及最大内积搜索的应用程序性能。
maximum inner product searchhashing methodnorm-ranging lshquery time complexitysimilarity metric
发现论文，激发创造
  • 用于亚线性时间最大内积搜索（MIPS）的非对称局部敏感哈希（ALSH）

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

    May, 2014

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

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

    Oct, 2014

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

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

    Oct, 2014

  • 具有理论保证的快速局部敏感哈希

    通过随机抽样和随机投影的组合，FastLSH 算法将 LSH 计算的时间复杂度从 O (n) 降低到 O (m)（其中 m < n），并具有可证明的 LSH 属性，是一种有希望替代经典 LSH 方案的方法。

    Sep, 2023

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

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

    Jul, 2015

  • 内积相似性连接的复杂性

    该论文系统研究了内积相似性连接问题，提出了新的上下界和基于线性草图的索引方法，并探讨了不对称性的影响。

    Oct, 2015

  • 通过张量化的随机投影来改进 LSH

    提供了一种基于 CP 和 tensor train (TT) 分解技术的 LSH 方法，适用于欧几里得距离和余弦相似度的张量数据，具有空间高效性。

    Feb, 2024

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

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

    Sep, 2019

  • 密度敏感哈希

    提出了一种名为密度敏感哈希（DSH）算法，它是局部敏感哈希（LSH）的扩展，利用数据的几何结构避免了纯随机投影的限制，并在大规模高维数据搜索中取得更好的性能。

    May, 2012

  • 高效的分布式局部敏感哈希

    本文提出了基于熵局部敏感哈希的分布式分层哈希方案，能够显著减少网络流量，提高实际应用程序的运行效率。

    Oct, 2012