论文标题
SAH：反向$ k $ - 最大内部产品搜索的转移不对称散列
SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner Product Search
论文作者
论文摘要
本文调查了一个新的但具有挑战性的问题，称为反向$ k $ - 毫米最大内部产品搜索（r $ k $ mips）。给定查询（项目）向量，一组项目向量和一组用户向量，R $ K $ MIPS的问题旨在找到一组用户向量，其内部产品带有查询矢量是查询和项目向量中最大的$ K $之一。我们提出了第一种亚次级时期算法，即不对称的散落哈希（SAH），以解决R $ K $ MIPS问题。为了加快项目向量上的最大内部产品搜索（MIP），我们设计了一种不变的不对称转换，并开发了一种新型的SublineAr-time转换转换不对称的不对称局部性敏感性哈希（SA-ALSH）方案。此外，我们设计了一种基于圆锥树的新阻塞策略，以有效修剪用户向量（批量）。我们证明，SAH实现了解决RMIP问题的理论保证。五个现实世界数据集的实验结果表明，SAH运行4 $ \ sim $ 8 $ \ times $ $ $ $ $ $ $ $ $ $ $ $ $ \ times $快于r $ k $ mips的最先进方法，而达到超过90 \％的F1得分。该代码可在\ url {https://github.com/huangqiang/sah}中获得。
This paper investigates a new yet challenging problem called Reverse $k$-Maximum Inner Product Search (R$k$MIPS). Given a query (item) vector, a set of item vectors, and a set of user vectors, the problem of R$k$MIPS aims to find a set of user vectors whose inner products with the query vector are one of the $k$ largest among the query and item vectors. We propose the first subquadratic-time algorithm, i.e., Shifting-aware Asymmetric Hashing (SAH), to tackle the R$k$MIPS problem. To speed up the Maximum Inner Product Search (MIPS) on item vectors, we design a shifting-invariant asymmetric transformation and develop a novel sublinear-time Shifting-Aware Asymmetric Locality Sensitive Hashing (SA-ALSH) scheme. Furthermore, we devise a new blocking strategy based on the Cone-Tree to effectively prune user vectors (in a batch). We prove that SAH achieves a theoretical guarantee for solving the RMIPS problem. Experimental results on five real-world datasets show that SAH runs 4$\sim$8$\times$ faster than the state-of-the-art methods for R$k$MIPS while achieving F1-scores of over 90\%. The code is available at \url{https://github.com/HuangQiang/SAH}.
