  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\%.
