Can I read Maximum Inner Product is Query-Scaled Nearest Neighbor on EtoBox?

Maximum Inner Product is Query-Scaled Nearest Neighbor by Chen, Tingyang; Fu, Cong; Wang, Kun; Ke, Xiangyu; Gao, Yunjun; Zhou, Wenchao; Ni, Yabo; Zeng, Anxiang is a scholarly article available to read on EtoBox.

What is Maximum Inner Product is Query-Scaled Nearest Neighbor about?

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 Proximity Graph with Spherical Pathway (PSP), designed to mitigate the issue of MIPS solutions clustering around large-norm vectors, and the implementation of Adaptive Early Termination (AET), which efficiently curtails the excessive exploration once an accuracy bottleneck is reached. Extensive experiments reveal the superiority of our method over existing

Author

Chen, Tingyang; Fu, Cong; Wang, Kun; Ke, Xiangyu; Gao, Yunjun; Zhou, Wenchao; Ni, Yabo; Zeng, Anxiang

Published

2025

Language

EN