Parallel Memory-Based Collaborative Filtering for Distributed Big Data Environments

Before we jump into recommender systems, the most imperative step should be to understand different categories of data processing systems referred to as Information Retrieval systems. Information retrieval (IR) can be defined as the process of using a source of data and extracting information pertinent to an inquiry done by, any user or any other system e.g., a movie based on genre from a streaming platform, a journal from a repository based on a subject, or results produced by the search engine based on a question asked by the user [1]. One the types of IR is recommender systems. Hence, we can define a recommender system (RS) as a subcategory of an information filtering system that calculates the most accurate rating a user would provide for an item [2]. RS as a software solution has its roots in the most basic human tendency of asking for suggestions or recommendations before trying out any new experience or object or even for making friends. The information provided by these systems helps the users make decisions like purchasing an item, renting a movie, etc. The recommendations presented are designed to assist individuals in making informed decisions across a range of contexts. This means that the primary objective of these systems is to provide personalized recommendations which is the major difference between recommender systems and information retrieval search engines [2]. Recommender systems have emerged as essential tools in electronic commerce, providing effective solutions for online users grappling with information overdose. Their significance lies in their ability to sift through vast amounts of data, enabling users to make informed decisions. These systems have become pivotal in addressing the challenges posed by the overwhelming volume of information on online platforms. Hence, numerous methods for generating recommendations have been put forward. Companies like Netflix, Amazon, Facebook, etc. have successfully applied and gained from these methods for recommending books, movies and friends. Any RS has two main objects: “Items” and “Users”. The topic or object for which the suggestions are generated is generally called “Item”. Normally, RS is meant to recommend a specific type of item like movies, books, songs, restaurants, etc. Such systems are mainly aimed at individuals (referred to as “User” in RS) who are relatively new in a certain domain, like people looking for hotel suggestions before visiting a new place. Interaction between the items and users is called “Transaction”. Transactions give us data about items, users and preferences. The recorded preferences of users act as an input to the RS. These inputs can be collected implicitly or explicitly. Explicit feedback [3] shows the direct preference of users for an item. Explicit ratings are mostly on a numerical scale like a range of 1 rating for worst and 5 being the best, like otherwise dislike, etc. Implicit feedback is extracted from user actions like the amount of time the user was on any given page, clicks performed by users on websites, whether the user purchased the item or watched the video, etc. Based on the way recommendations are generated, RS can be classified as given in Figure 1.

1.png

Figure 1. Type of recommendation system

(1) Collaborative filtering: Collaborative filtering [4] recommender systems leverage the preferences and behaviours of other users to suggest items or content to a particular user. By analysing the choices and interactions of a diverse user base, these systems identify patterns and correlations, allowing them to generate personalized recommendations. This approach helps users navigate the abundance of available options, making their online experience more tailored and relevant. Through sophisticated algorithms and data analysis, recommender systems enhance user engagement and satisfaction by presenting them with choices aligned with their interests and preferences. For instance, a recommendation of a film for a viewer can be grounded on the explicit or implicit feedback given by various other viewers who have watched the movie.

(2) Content-based: Content-based [5] recommender systems use the previous interactions of the uses with the system and item properties of the items under consideration. Such systems might recommend movies based on the genre of the previously watched movies of the users or a book recommender tool might suggest books of the same author whose other books have already been read by the same user.

(3) Demographic: These systems use the date of birth, sex of the user, and their current geographical location to generate suggestions for the user. For instance, this type of recommender would recommend the product to any user on the same lines as the products that users of the same age and gender have purchased.

(4) Knowledge-based: Industry or domain-specific knowledge is used by such systems to provide useful suggestions to the user. The best example is a system suggesting a recipe to the user, considering the dietary restrictions and the ingredients they have on hand.

(5) Community-based: Community-based recommender systems recommend items to a user relying on the predilections of user clusters having similar features. For instance, this type of recommender would use all views of all users of the same online forum to which another user belongs and suggest a movie rated highly by the users of the forum.

(6) Hybrid filtering: These recommender systems are built using a combination of systems mentioned above.

2.1 Content-based filtering algorithms

Content-based filtering (CBF) generates a feature set of items and preference or behaviour profiles for users based on additional information about user demography, online behavior, their friend network, and the properties of items used by customers. CBF is classified as content-based when it provides recommendations grounded in the content details of items. Conversely, when these recommendations rely on the contextual information of users, CBF is termed context-based. In most situations, extracting relevant information about users or items becomes challenging due to a lack of information or information overload. This limits the performance and application of CBF.

2.2 Collaborative filtering algorithms

The majority of the recommender systems are based on Collaborative filtering algorithms. It can be defined as a method that generates suggestions, i.e., filters the information related to the choices of any person by gathering information from a large quantity of other people, i.e., collaborative filtering [6]. Breese et al. [7] categorized CF techniques into systems which are based on memory while another type of system is built on models.

2.2.1 Model-based CF techniques

In the model-based approach, the system generates parameters to model the behavior of users and features of items, which enables it to make suggestions using the created parameters. Filtering techniques are collaborative in nature and build learning models based on machines for predicting ratings that an item might get from the user. These models are trained on a dataset of user ratings and item features. Once the models are trained, they can forecast the most probable rating an item would get from a specific user, even in scenarios where the user-item interaction would not have occurred earlier and no rating data is recorded for this user-item pair. As the main of such techniques is to predict rating, probability of purchase, etc., these systems are most commonly configured as supervised learning problems.

2.2.2 Memory-based CF techniques

Memory-based collaborative filtering techniques are relatively simple to implement and can be very effective for generating personalized recommendations. Memory or neighbourhood-based CF are implemented by calculating distance or similarity metrics. In memory-based CF, recommendations are based on similarities among users [8] or items [9].

(1) User-item Collaborative Filtering: items used or purchased or rated by users similar to us. Such systems first find users similar to the user under consideration and then generate recommendations for users based on their purchase or rating history.

(2) Item-item Collaborative Filtering: based on the segregation that suggests that users who show interest in specific items are more likely to be interested in these items. Here, we first find similarities among a bunch of items and recommend items that are most similar to items already rated by that user.

A detailed comparison in terms of the various characteristics of both these methods can be found in Table 1.

Table 1. Comparison of memory and model-based CF

2.3 Challenges of the recommender system

Recommender systems are complex algorithms that use data to predict what users will like. They are used in various applications, like online shopping, streaming services, and social media. However, recommender systems also face several challenges, including:

Lack of data: Recommender systems need data to learn user preferences and make accurate recommendations. However, it is quite possible that there is not enough data for the users with very specific interests and this makes it very difficult to make useful and correct recommendations.

Cold start problem: It is a phenomenon faced by a recommendation system when a new user or item enters the system and recommendations have to be generated for such users or items. Being new to the system there is no associated data for such users or items. This makes it very hard to provide recommendations when no data is available for the user’s interests or the item’s popularity. Thus, making it very challenging while generating recommendations.

Scalability: The most critical feature of any Recommender system should be its ability to scale up to the ever-increasing volume of data being generated by users and items. As most of the recommender systems run on very complex algorithms which are computationally demanding, scalability becomes one of the biggest challenges that should be considered while designing any recommender systems.

Sparsity: As the majority of the users do not interact with the majority of the items, the user-item matrix in a recommender system is often very sparse. This means data is not available for most of the user-item pairs. The absence of data makes it very difficult to make useful recommendations and understand the preferential pattern of the user or the popularity of items.

Bias: The methods or even data used to generate recommendations can be the source of an inherent bias towards certain items or users. Once the bias is present in the recommendations there is a very high chance of the same items being recommended to the majority of users and not taking into account the actual preferences of the user.

Privacy: There is an automatic concern relating to the collection and storage of data for making more accurate recommendations. This data can be transactional data or implicit data like browsing history and purchase history. This is not only a security concern but also raises ethical concerns as to what is the extent to which we should collect data without infringing the privacy of any user.

Apart from the challenges discussed above, there are numerous other challenges faced by any recommender system. It should be flexible enough to cater to the ever-evolving preferences of the user and also consider the new items which are regularly added to the inventory. It also should be robust to handle attacks such as shilling attacks. A shilling attack is an attack where the system is flooded by fake user profiles and their review of items which can either promote or paint a bad review for any item. Even with such challenges, the recommender system is a very useful tool which not only helps users identify the most suitable items for them but also discovers new content and products which they would normally not try.

The most practical implementation of a memory-based CF is calculating the distance metric like cosine similarity [19], Pearson correlation [30] and Jaccard coefficient. We have focused on cosine similarity. It measures the similarity of two items, A and B, by measuring the cosine of the angle between the two vectors. The original formula for the cosine similarity is as given in Eq. (1):

$\operatorname{Similarity}(A, B)=\operatorname{Cos}(A, B)=\frac{|A \cdot B|}{\|A\| *\|B\|}$                          (1)

In this paper, item-item CF is implemented by using cosine similarity in parallelly in a parallel manner. For this parallel implementation, the proposed calculation of cosine similarity is given in Eq. (2):

$\operatorname{Similarity}(A, B)=\frac{|A|^2+|B|^2-C^2}{2 *|A| *|B|}$                      (2)

where, A and B are item vector and C is the Euclidean distance between A and B.

When applying cosine similarity in item-item CF each vector corresponds to an item and vector dimension corresponds to users who have rated the item.

The following algorithm [19] provides an approach by calculating the similarity between a single item and all related items.

The computation described above is the extremely time intensive. To improve the efficiency, it requires reducing the problem into manageable proportions. Number of users and items range in millions and become unmanageable. The approach taken in our work is to perform independent calculations in a parallelized and distributed manner. To achieve parallelization, the following steps are required.

Once we have partitioned data, we can carry on with further transformations. Given below are transformations applied.

Our approach has multiple facets, which makes it more efficient.

1. The magnitude of item vectors is calculated in a parallelized manner.

2. Use of Euclidean distance for calculating cosine similarity.

3. Calculation of similarity in a distributed Spark cluster.

The Eq. (1) is slower because it computes the sum of products whereas Eq. (2) calculates sum of square distances. Multiplication is an expensive operation compared to subtraction and square. The Eq. (2) does not require the computation of the product, and is therefore faster. We break down and discuss each component of both formulae in the next paragraph.

When we calculate the square root of the sum of the squares of each corresponding element of any vector, we can say that we have calculated the norm of that particular vector is defined as the square root of the sum of the squares of its elements. For example, let us consider a vector A, the norm can be calculated by Eq. (3).

$\|A\|=\sqrt{\sum A^2}$                (3)

We need to partition vector A into smaller blocks and then compute the norm of each block in parallel when the norm has to be calculated in a distributed environment. Then, all the intermediate norm of each block is summed up to achieve the final norm of the vector. Given, two vectors A and B, the dot product can be calculated by computing the sum of the products of their corresponding elements. This is also called a scalar product of the two vectors which is calculated using Eq. (4).

$A \cdot B=\sum A * B$                   (4)

We need to partition the vectors A and B into smaller blocks and then compute the dot product of each block in parallel in a distributed environment. Then we can achieve the final dot product of the two vectors by adding up the dot products of the blocks. The Euclidean distance between two vectors is defined as the square root of the sum of the squares of the differences of their corresponding elements. In other words, for two vectors A and B, the Euclidean distance is given by: This can also be computed in a distributed environment by partitioning vectors A and B into smaller blocks and computing the parallel Euclidean distance between each block. Once the Euclidean distance between each block is computed, the overall Euclidean distance between the vectors can be computed by summing the Euclidean distances between the blocks.

In the proposed Eq. (1), we have precalculated the magnitude of the item vector, so this calculation does not contribute to execution time when calculating similarity in the final step. As the data is partitioned based on items, all the dimensions corresponding to users rating the same item are present in a single partition. This ensures minimum shuffle between the partitions.

Table 2. Comparison of number of mapper and reducers

It can be understood from the Table 2 that number of MapReduce jobs is very important. Our work uses optimum number of mappers and reducers. Hence, we get the improved results.

4.1 Roles of distributed system in recommendation

Apart from the calculation changes. We also made sure to use of distributed and parallel computing as the two main weapons to fight the challenges and enhance the performance of these recommendation engines.

These programming paradigms have a two-pronged approach, where the computation work is spread or distributed across multiple computers whereas parallel processing utilized the multiple cores of each machine and the workload is further distributed in multiple cores of each machine. Furthermore, these systems can be upgraded by using a large number of commodity hardware and by scaling parallelly thereby reducing the cost of expensive vertical upgrades. This collection of computing resources makes it possible to handle large datasets and enables recommender systems to generate real-time recommendations.

There are a bunch of advantages provided by the use of distributed and parallel computation:

Scalability: A distributed system can easily scale to match the growing rate of data, users and items. As such systems scale up horizontally which means adding commodity hardware instead of expensive servers, it is much cheaper and becomes more viable for the future too. The proposed work uses the user-item interaction matrix which is partitioned over the distributed environment. The system can distribute the new workload across nodes when new data and users are added. This ensures that the system can easily handle larger datasets. If required we can just add more inexpensive hardware instead of high-end servers. Thus, horizontal scaling ensures scalability in a much cheaper manner than vertical scaling.

Faster Training: With the use of parallel processing the algorithms itself can be parallelized. This expedites the calculation of values like similarities. Thus, in turn improving the speed of the training of algorithms many folds, enabling them to learn from extensive datasets quickly. This use of parallel processing confirms that similarities and recommendations are always updated with the latest user-item interactions. Our implementation uses parallel processing as each node has 4 CPU cores. This speed up the calculations of the similarities as larger calculations are broken down into smaller tasks. This can be easily ascertained using the speedup measure of the results.

Real-time Recommendations: When distributed and parallel data processing is combined, the prospect of real-time recommendations becomes a possibility. This ensures that all recommendations are always updated with the most recent trends of user preferences and item popularity. In the proposed solution Apache Spark has been used as the engine which provides in-memory processing. This further compliment the new formula by providing near real-time calculations, so that similarity values can be always recalculated if there is any change in user preferences and popularity of the items.

Complex Models: Such systems also allow the researchers to use more sophisticated methods like deep learning-based recommendation models. These models can emulate the behavior of the users and user-item relations much more efficiently. In our approach, due to the use of Apache Spark which supports a large number of data science and ML libraries. We can easily build further complex models.

These implementation techniques have shown a good improvement in the execution time of cosine similarity; the results are discussed in detail in the next section.

All the experimental results provided above showcase that the proposed method provides improved scalability and performance. These features are critical for a recommendation system to be considered useful in a real-world scenario. Given below are a few important considerations showcasing the usefulness of this approach:

(1) Improved execution time: In the above results it is clear that execution time is nearly reduced to half of that of the original formula. For example, in Table 3 for 2000000 rows of data execution time is 10000 seconds as compared to that of 32000 seconds in the original cosine formula.

(2) Better parallelization: The greater speedup factor noted in Table 5 also showcases that our implementation is very much suitable for parallel execution as increasing the number of cores reduces the execution time by a factor of more than 3 whereas the execution time in the traditional approach only improved by a factor of 2.

(3) Ability to handle more users: As the volume of the data is increased thereby increasing the number of users the results in Table 3 again show that the proposed method can manage increment in the data without a proportion increase in execution time.

(4) Better resource utilization: The proposed work showcases an improved efficiency of 0.82 compared to 0.55 of the original approach. This means that our approach utilizes the available resources more effectively than the current approach.

There are many papers which have focused on the parallel implementation of collaborative filtering. However, the focus has always been on using the direct implementations of existing algorithms. We have proved with the experiments that even adjusting the derivation of cosine similarity can tremendously improve execution time. Further, we can also safely state that the formula used in this paper has a better speedup. The use of the new formula also utilizes the resources much more efficiently. All these parameters remain consistently in favour of using the new formula.

Though the use of a suitable formula did improve the efficiency of the memory-based collaborative filtering, there were no changes done to improve the accuracy. We plan to focus next on improving the accuracy of such a system. This would provide us with more efficient and accurate novel approaches to make sense of the ever-growing data.