Timezone: »

 
Poster
A Greedy Approach for Budgeted Maximum Inner Product Search
Hsiang-Fu Yu · Cho-Jui Hsieh · Qi Lei · Inderjit Dhillon

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #89
in Posters Wed »

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

Keywords: Embedding Approaches · Matrix and Tensor Factorization · Recommender Systems · Algorithms · Speech Recognition
[ Paper] 

Author Information

Hsiang-Fu Yu (U Texas)
Cho-Jui Hsieh (UCLA, Google)
Qi Lei (University of Texas at Austin)
Inderjit Dhillon (University of Texas at Austin)

More from the Same Authors