Index partitioning through a bipartite graph model for faster similarity search in recommendation systems

摘要

Scalability of a recommendation system is an important factor for large e-commerce sites containing millions of products visited by millions of users. Similarity search is the core operation in recommendation systems. In this paper, we explain a framework to alleviate performance bottleneck of similarity search for very large-scale recommendation systems. The framework employs inverted index for real-time similarity search and handles dynamic updates. As the inverted index gets larger, retrieving recommendations become computationally expensive. There are various works devoted to solve this problem, such as clustering and preprocessing to compute recommendations offline. Our solution is based on bipartite graph partitioning for minimizing the affinity between entities in different partitions. Number of operations in similarity search is reduced by executing search within the closest partitions to the query. Parts are balanced, so that computational loads of partitions are almost the same, which is significant for reducing the computational cost. Sequential experiments with several different recommendation approaches and large datasets consisting of millions of users and items validate the scalability of the proposed recommendation framework. Accuracy drops only by a small factor due to partitioning, if any. Even slight improvements in recommendation accuracy are observed in our collaborative filtering experiments.