FEXIPRO: Fast and exact inner product retrieval in recommender systems

Hui Li, Tsz Nam Chan, Man Lung Yiu, Nikos Mamoulis

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

23 Citations (Scopus)

Abstract

Recommender systems have many successful applications in e-commerce and social media, including Amazon, Netflix, and Yelp. Matrix Factorization (MF) is one of the most popular recommendation approaches; the original user-product rating matrix R with millions of rows and columns is decomposed into a user matrix Q and an item matrix P, such that the product QTP approximates R. Each column q (p) of Q (P) holds the latent factors of the corresponding user (item), and qTp is a prediction of the rating to item p by user q. Recommender systems based on MF suggest to a user in q the items with the top-k scores in qTP. For this problem, we propose a Fast and EXact Inner PROduct retrieval (FEXIPRO) framework, based on sequential scan, which includes three elements. First, FEXIPRO applies an SVD transformation to P, after which the first several dimensions capture a large percentage of the inner products. This enables us to prune item vectors by only computing their partial inner products with q. Second, we construct an integer approximation version of P, which can be used to compute fast upper bounds for the inner products that can prune item vectors. Finally, we apply a lossless transformation to P, such that the resulting matrix has only positive values, allowing for the inner products to be monotonically increasing with dimensionality. Experiments on real data demonstrate that our framework outperforms alternative approaches typically by an order of magnitude.
Original languageEnglish
Title of host publicationSIGMOD 2017 - Proceedings of the 2017 ACM International Conference on Management of Data
PublisherAssociation for Computing Machinery
Pages835-850
Number of pages16
VolumePart F127746
ISBN (Electronic)9781450341974
DOIs
Publication statusPublished - 9 May 2017
Event2017 ACM SIGMOD International Conference on Management of Data, SIGMOD 2017 - Hilton Chicago, Chicago, United States
Duration: 14 May 201719 May 2017

Conference

Conference2017 ACM SIGMOD International Conference on Management of Data, SIGMOD 2017
CountryUnited States
CityChicago
Period14/05/1719/05/17

ASJC Scopus subject areas

  • Software
  • Information Systems

Cite this