• Topics:
• Big Data
• Greedy Method
• Recommender Systems

Download: pdf

Citation

• A Greedy Approach for Budgeted Maximum Inner Product Search (pdf, software)
  H. Yu, C. Hsieh, Q. Lei, I. Dhillon.
  In Neural Information Processing Systems (NIPS), December 2017.
  
  Bibtex:
  
  @inproceedings{yu2017agreedya, author = "Hsiang-Fu Yu AND Cho-Jui Hsieh AND Qi Lei AND Inderjit S. Dhillon", title = "A Greedy Approach for Budgeted Maximum Inner Product Search", booktitle = "Neural Information Processing Systems (NIPS)", year = "2017", month = "dec", abstract = "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%." }