Neyshabur and Srebro proposed Simple-LSH, which is the state-of-the-art
hashing method for maximum inner product search (MIPS) with performance
guarantee. We found that the performance of Simple-LSH, in both theory and
practice, suffers from long tails in the 2-norm distribution of real datasets.
We propose Norm-ranging LSH, which addresses the excessive normalization
problem caused by long tails in Simple-LSH by partitioning a dataset into
multiple sub-datasets and building a hash index for each sub-dataset
independently. We prove that Norm-ranging LSH has lower query time complexity
than Simple-LSH. We also show that the idea of partitioning the dataset can
improve other hashing based methods for MIPS. To support efficient query
processing on the hash indexes of the sub-datasets, a novel similarity metric
is formulated. Experiments show that Norm-ranging LSH achieves an order of
magnitude speedup over Simple-LSH for the same recall, thus significantly
benefiting applications that involve MIPS.

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