# SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search

arXiv: https://arxiv.org/abs/2211.12751 · HTML: https://mlsanity.com/paper/2211.12751/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 23 Nov 2022.

## Builds on (most cited first, 13 of 13)

- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Quantization based Fast Inner Product Search](https://mlsanity.com/paper/1509.01469/) (2015)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1410.5410/) (2014)
- [A Greedy Approach for Budgeted Maximum Inner Product Search](https://mlsanity.com/paper/1610.03317/) (2016)
- [Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring](https://mlsanity.com/paper/2004.05345/) (2020)
- [Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search](https://mlsanity.com/paper/1911.04654/) (2019)
- [Norm-Ranging LSH for Maximum Inner Product Search](https://mlsanity.com/paper/1809.08782/) (2018)
- [Understanding and Improving Proximity Graph based Maximum Inner Product Search](https://mlsanity.com/paper/1909.13459/) (2019)
- [Reverse Maximum Inner Product Search: How to efficiently find users who would like to buy my item?](https://mlsanity.com/paper/2110.07131/) (2021)
- [Diamond Sampling for Approximate Maximum All-pairs Dot-product (MAD) Search](https://mlsanity.com/paper/1506.03872/) (2015)
- [Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search](https://mlsanity.com/paper/1908.08656/) (2019)

## Built on by (most cited first, 1 of 1)

- [Very Efficient Listwise Multimodal Reranking for Long Documents](https://mlsanity.com/paper/2605.11864/) (2026)

## Abstract (arXiv)

This paper investigates a new yet challenging problem called Reverse k-Maximum Inner Product Search (RkMIPS). Given a query (item) vector, a set of item vectors, and a set of user vectors, the problem of RkMIPS 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 RkMIPS 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~8× faster than the state-of-the-art methods for RkMIPS while achieving F1-scores of over 90%. The code is available at urlhttps://github.com/HuangQiang/SAH.