A Greedy Approach for Budgeted Maximum Inner Product Search
This addresses the need for flexible trade-offs between efficiency and quality in MIPS, particularly for applications like recommender systems, though it appears incremental as it builds on existing MIPS methods.
The paper tackles the Maximum Inner Product Search (MIPS) problem with a computational budget, developing the Greedy-MIPS algorithm that runs 200x faster than naive methods while achieving over 75% top-5 precision on a dataset of 500,000 vectors.
Maximum Inner Product Search (MIPS) is an important task in many machine learning applications such as the prediction phase of a low-rank matrix factorization model for a recommender system. There have been some works on how to perform MIPS in sub-linear time recently. However, most of them do not have the flexibility to control the trade-off between search efficient and search quality. In this paper, we study the MIPS problem with a computational budget. By carefully studying the problem structure of MIPS, we develop a novel Greedy-MIPS algorithm, which can handle budgeted MIPS by design. While simple and intuitive, Greedy-MIPS yields surprisingly superior performance compared to state-of-the-art approaches. As a specific example, on a candidate set containing half a million vectors of dimension 200, Greedy-MIPS runs 200x faster than the naive approach while yielding search results with the top-5 precision greater than 75\%.