Fast algorithms to evaluate collaborative filtering recommender systems

Before deploying a recommender system, its performance must be measured and understood. So evaluation is an integral part of the process to design and implement recommender systems. In collaborative filtering, there are many metrics for evaluating recommender systems. Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) are among the most important and representative ones. To calculate MAE/RMSE, predicted ratings are compared with their corresponding true ratings. To predict item ratings, similarities between active users and their candidate neighbors need to be calculated. The complexity for the traditional and naive similarity calculation corresponding to user u and user v is quadratic in the number of items rated by u and v. In this paper, we explore the mathematical regularities underlying the similarity formulas, introduce a novel data structure, and design linear time algorithms to calculate the similarities. Such complexity improvement shortens the evaluation time and will finally contribute to increasing the efficiency of design and development of recommender systems. Experimental results confirm the claim.