On identifying k-nearest neighbors in neighborhood models for efficient and effective collaborative filtering

Neighborhood models (NBMs) are the methods widely used for collaborative filtering in recommender systems. Given a target user and a target item, NBMs find k most similar users or items (i.e., k-nearest neighbors) and make a prediction of a target user on an item based on the rating patterns of those neighbors on the item. In NBMs, however, we have a difficulty in satisfying both the performance and accuracy together. In order to pursue an accurate recommendation, NBMs may find the k-nearest neighbors at every recommendation request to exploit the latest ratings, which requires a huge amount of computation time. Alternatively, NBMs may search for the k-nearest neighbors offline, which consequently results in inaccurate recommendation as time goes by, or even may not able to deal with new users or new items, because they cannot exploit the latest ratings generated after the k-nearest neighbors are determined. In this paper, we propose a novel approach that finds the k-nearest neighbors efficiently by identifying only those users and items necessary in computing the similarity. The proposed approach enables NBMs not to require any offline similarity computations but to exploit the latest ratings, thereby resolving speed-accuracy tradeoff successfully. We demonstrate the effectiveness of the proposed approach through extensive experiments.