Scalable Hierarchical Recommendations Using Spatial Auto Correlation

Abstract

Collaborative Filtering (CF) is one of the most successful and widely used approaches behind Recommendation Algorithms. CF algorithms use the known preferences of a group of users to make recommendations or predictions of the unknown preferences for other users. In this paper, we deal with the Scalability issue which is one of the main challenges to the CF algorithms. In Collaborative Filtering, nding similarity amongst N users is an O(N2) process. If N is large then similarity computation becomes very expensive. In this work, we propose a Quadtree based user partitioning technique that partitions the entire users' space into regions based on the location. We develop a Spatially Aware Recommendation Algorithm, where the Recommendation Algorithm is applied separately to each region and therefore allows us to reduce the quadratic complexity associated with the CF process. The proposed work tries to measure the Spatial Autocorrelation indices, such as Geary's index in the regions or cells formed by the Quadtree decomposition. One of the main objectives of our work is to reduce the running time as well as maintain a good quality of recommendation. This approach of recommendation using the decomposition method makes our algorithm feasible to work with large datasets. We have tested our algorithms on the MovieLens and the Book-Crossing datasets.