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

ICMLOct, 2014

On Symmetric and Asymmetric LSHs for Inner Product Search

Behnam Neyshabur, Nathan Srebro

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

Abstract

We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li argue that there is no →

locality sensitive hashes inner product similarity symmetric lsh asymmetric lsh guarantees

发现论文，激发创造

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

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

May, 2014

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

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

Oct, 2014

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

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

Sep, 2018

内积相似性连接的复杂性

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

Oct, 2015

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

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

Oct, 2012

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

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

Feb, 2024

用于角度距离的实用和最优 LSH

证明了存在一种角距离的局部敏感哈希族，可以产生一个渐进最优运行时间指数的近邻搜索算法。同时，提出了这种算法的多探针版本，并在真实和合成数据集上进行实验评估。