A Scalable K-Nearest Neighbor Algorithm for Recommendation System Problems

Memory-based classification techniques are commonly used for modeling recommendation problems. They rely on the intuition that similar users and/or items behave similarly, facilitating user-toitem, item-to-item, or user-to-user proximities. A significant drawback of memory-based classification techniques is that they perform poorly with large scale data. Thus, using the off-the-shelf classification techniques for recommendation problems generally lead to impractical computational costs. In this study, we propose a recommendation problem-specific enhancement for a widely known memory-based classification algorithm, K-Nearest Neighbor. For this purpose, the movie recommendation problem is selected, and the scalability of the proposed enhancement is evaluated on three publicly available datasets. In the proposed enhancement, user- and item-proximities are pre-calculated during the first offline recommendation, while an auxiliary data structure is constructed for keeping user-to-user proximities. The stored neighborhood information is then facilitated in order to speed up later recommendations. The experiments show that the proposed algorithm has performed superior to both the classical classification technique and the state-of-the-art off-the-shelf toolkits.