A Greedy Approach for Budgeted Maximum Inner Product Search
Maximum Inner Product Search (MIPS) is an important task in many machine learning applications such as the prediction phase of low-rank matrix factorization models and deep learning models. Recently, there has been substantial research on how to perform MIPS in sub-linear time, but most of the existing work does not have the flexibility to control the trade-off between search efficiency and search quality. In this paper, we study the important problem of MIPS 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%.
The aim of the paper is to propose a new greedy approach for Maximum Inner Product Search problem: given a candidate vector, retrieve a set of vectors with maximum inner product to the query vector. This is a crucial step in several machine learning and data mining algorithms, and the state of the art methods work in sub-linear time recently. The originality of the paper is to study the MIPS problem under a computational budget. The proposed approach achieves 
better balance between search efficiency and quality of the retrieved vectors, and  does not require a nearest neighbor search phase, as commonly done by state of the art approaches. The authors claim impressive runtime results (their algorithm is 200x faster than the naive approach), and a top-5 precision  greater than 75%. 
	  
	  
	  The paper is very dense (the space between two lines seems smaller than the one in the template). However, the paper is well-written and the procedure is well-explained. The proposed method seems also quite original, and comes with theoretical guarantees. The technical results seem sound.
	  
	  Some remarks:
	  
	  Figure 1 should be placed at the top of P.5, it is a bit difficult to follow without the later explanations.
	  
	  The bound used in P.4 needs to be more studied, in order to find, for instance, some properties (or better, an approximation). This bound is a key point of this procedure, and it is used at the beginning.
	  
	  P.5 "visit (j,t) entries of Z": (j,t) is a cell in the matrix Z, however you consider this notation as a number. Maybe "j \times t" entries?
	  
	  The reviewer would be interested to have access to the source code of the algorithm and the data, so as he can reproduce the expriments?