2016/10/11 by Hsiang‐Fu Yu, Hsiang-Fu Yu, Cho-Jui Hsieh +7 · 1 citation
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Computer science #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Greedy algorithm #Machine Learning (cs.LG) #Mathematical optimization #Mathematics #Product (mathematics) #Recommender Systems and Techniques #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.1610.03317
arxiv created 2016/10/11 · openalex publication_date 2016/10/11 · arxiv updated 2016/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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%.