# Understanding and Improving Proximity Graph based Maximum Inner Product Search

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2019.

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

- [A Comprehensive Survey on Trustworthy Recommender Systems](https://mlsanity.com/paper/2209.10117/) (2022)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search](https://mlsanity.com/paper/2211.12751/) (2022)
- [Approximate Diverse k-nearest Neighbor Search in Vector Database](https://mlsanity.com/paper/2510.27243/) (2025)

## Abstract (arXiv)

The inner-product navigable small world graph (ip-NSW) represents the state-of-the-art method for approximate maximum inner product search (MIPS) and it can achieve an order of magnitude speedup over the fastest baseline. However, to date it is still unclear where its exceptional performance comes from. In this paper, we show that there is a strong norm bias in the MIPS problem, which means that the large norm items are very likely to become the result of MIPS. Then we explain the good performance of ip-NSW as matching the norm bias of the MIPS problem - large norm items have big in-degrees in the ip-NSW proximity graph and a walk on the graph spends the majority of computation on these items, thus effectively avoids unnecessary computation on small norm items. Furthermore, we propose the ip-NSW+ algorithm, which improves ip-NSW by introducing an additional angular proximity graph. Search is first conducted on the angular graph to find the angular neighbors of a query and then the MIPS neighbors of these angular neighbors are used to initialize the candidate pool for search on the inner-product proximity graph. Experiment results show that ip-NSW+ consistently and significantly outperforms ip-NSW and provides more robust performance under different data distributions.