Making top-K predictions for state-of-the-art Matrix Factorization models requires solving the Maximum Inner Product Search problem. Solving MIPS can be computationally expensive, thus spurring the recent development of several indexing techniques for this task. These techniques generally exploit similarity between user or item weights in the models to accelerate predictions. In this paper, we show that the current state of the art does not always outperform brute-force matrix multiplication: these models may have significantly less similarity than can be exploited by these techniques. To address this problem, we propose RecOpt, a system that uses an efficient, sampling-based estimation technique to automatically choose between indexing or brute force. In addition, we propose a new baseline indexing scheme, RecDex, that can leverage blocked linear algebra to improve indexing-based serving performance . Together, RecOpt and RecDex outperform state-of-the-art indexes by 3.2\times on average, and up to 10.9\times, on widely studied models for recommendations and MIPS .
Exact Maximum Inner Product Search (MIPS) is an important task that is widely pertinent to recommender systems and high-dimensional similarity search. The brute-force approach to solving exact MIPS is computationally expensive, thus spurring recent development of novel indexes and pruning techniques for this task. In this paper, we show that a hardware-efficient brute-force approach, blocked matrix multiply (BMM), can outperform the state-of-the-art MIPS solvers by over an order of magnitude, for some -- but not all -- inputs. In this paper, we also present a novel MIPS solution, MAXIMUS, that takes advantage of hardware efficiency and pruning of the search space. Like BMM, MAXIMUS is faster than other solvers by up to an order of magnitude, but again only for some inputs. Since no single solution offers the best runtime performance for all inputs, we introduce a new data-dependent optimizer, OPTIMUS, that selects online with minimal overhead the best MIPS solver for a given input . Together, OPTIMUS and MAXIMUS outperform state-of-the-art MIPS solvers by 3.2\times on average, and up to 10.9\times, on widely studied MIPS datasets .
R
Making top-K predictions for state-of-the-art Matrix Factorization models requires solving the
Exact
R
problem. Solving MIPS can be
(MIPS) is an important task that is widely pertinent to recommender systems and high-dimensional similarity search. The brute-force approach to solving exact MIPS is
D
the
R
several indexing
novel indexes and pruning
D
These techniques generally exploit similarity between user or item weights in the models to accelerate predictions.
R
the current state of the art does not always outperform
a hardware-efficient
R
matrix multiplication: these models may have significantly less similarity than can be exploited by these techniques. To address this problem, we propose RecOpt, a system that uses an efficient, sampling-based estimation technique to automatically choose between indexing or brute force. In addition, we propose a new baseline indexing scheme, RecDex, that can leverage blocked linear algebra to improve indexing-based serving performance
approach, blocked matrix multiply (BMM), can outperform the state-of-the-art MIPS solvers by over an order of magnitude, for some -- but not all -- inputs. In this paper, we also present a novel MIPS solution, MAXIMUS, that takes advantage of hardware efficiency and pruning of the search space. Like BMM, MAXIMUS is faster than other solvers by up to an order of magnitude, but again only for some inputs. Since no single solution offers the best runtime performance for all inputs, we introduce a new data-dependent optimizer, OPTIMUS, that selects online with minimal overhead the best MIPS solver for a given input
R
RecOpt and RecDex
OPTIMUS and MAXIMUS
R
indexes
MIPS solvers
R
models for recommendations and MIPS
MIPS datasets