# Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2014.

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

- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Rethinking the Role of Token Retrieval in Multi-Vector Retrieval](https://mlsanity.com/paper/2304.01982/) (2023)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering](https://mlsanity.com/paper/2109.05773/) (2021)
- [Pistis-RAG: Enhancing Retrieval-Augmented Generation with Human Feedback](https://mlsanity.com/paper/2407.00072/) (2024)
- [Implicit Two-Tower Policies](https://mlsanity.com/paper/2208.01191/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [Query-Response Interactions by Multi-tasks in Semantic Search for Chatbot Candidate Retrieval](https://mlsanity.com/paper/2208.11018/) (2022)
- [SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search](https://mlsanity.com/paper/2211.12751/) (2022)
- [A Fast Randomized Algorithm for Massive Text Normalization](https://mlsanity.com/paper/2110.03024/) (2021)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [LIME: Link-based user-item Interaction Modeling with decoupled xor attention for Efficient test time scaling](https://mlsanity.com/paper/2510.18239/) (2025)

## Abstract (arXiv)

Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. Asymmetric transformations before hashing were the key in solving MIPS which was otherwise hard. In the prior work, the authors use asymmetric transformations which convert the problem of approximate MIPS into the problem of approximate near neighbor search which can be efficiently solved using hashing. In this work, we provide a different transformation which converts the problem of approximate MIPS into the problem of approximate cosine similarity search which can be efficiently solved using signed random projections. Theoretical analysis show that the new scheme is significantly better than the original scheme for MIPS. Experimental evaluations strongly support the theoretical findings.