Maximum Inner Product is Query-Scaled Nearest Neighbor

Download PDF

Abstract

Maximum Inner Product Search ( MIPS ) for high-dimensional vectors is pivotal across databases, information retrieval, and artificial intelligence. Existing methods either reduce MIPS to Nearest Neighbor Search ( NNS ) while suffering from harmful vector space transformations, or attempt to tackle MIPS directly but struggle to mitigate redundant computations due to the absence of the triangle inequality. This paper presents a novel theoretical framework that equates MIPS with NNS without requiring space transformation, thereby allowing us to leverage advanced graph-based indices for NNS and efficient edge pruning strategies, significantly reducing unnecessary computations. Despite a strong baseline set by our theoretical analysis, we identify and address two persistent challenges to further refine our method: the introduction of the P roximity Graph with S pherical P athway ( PSP ), designed to mitigate the issue of MIPS solutions clustering around large-norm vectors, and the implementation of A daptive E arly T ermination (AET), which efficiently curtails the excessive exploration once an accuracy bottleneck is reached. Extensive experiments reveal that our method is superior to existing state-of-the-art techniques in search efficiency, scalability, and practical applicability. Compared with state-of-theart graph-based methods, it achieves an average 35% speed-up in query processing and a 3 × reduction in index size. Notably, our approach has been validated and deployed in the search engines of Shopee, a well-known online shopping platform. Our code and an industrial-scale dataset for offline evaluation will also be released to address the absence of e-commerce data in public benchmarks.