State-of-the-art

Collaborative Filtering (CF) is a thriving subfield of machine learning, and several surveys expose the achievements in this fields [1,2]. It became popular in the late 90's with the spread of online services that use recommender systems, such as Amazon.com, Yahoo! and Netflix. CF solutions in the current literature are often divided in two main groups: memory-based and model-based [3].

Memory-based algorithms operate on the entire set of ratings to generate predictions. The idea behind this long-lived family of algorithms is to compute a similarity score, which reflects the distance between two users or two items. Predictions are then computed by looking at the ratings of the k most similar users or items (k-nearest neighbor) [4,5]. Memory-based methods are used in a lot of real-world systems because of their simple design and implementation. However, they impose several scalability limitations that make their use impractical when dealing with large amounts of data. The slope one algorithms [6] were proposed to make faster prediction than memory-based algorithms, but they were unable to overcome the scalability issues of the latter.

Model-based approaches have been investigated to overcome the shortcomings of memory-based algorithms. They use the set of available ratings to estimate or learn a model and then apply this model to make rating predictions. There have been several model-based CF approaches proposed in the literature, which use almost every existing machine learning technique. In this multitude of algorithms, the most successful are by far those based on low-dimensional factor models. The idea behind such techniques is that attitudes or preferences can be described by a small number of unobserved factors, that can be thought of as representing user communities (like-minded users) or item communities (genres). The Netflix Prize definitively consecrated latent factor models, in particular those based on matrix factorization (MF) [7,8,9,10]. These methods aims at obtaining two lower rank matrices P and Q, for users and items respectively, from the global matrix of ratings R, with minimal loss of information. The fact that in real-word datasets most entries in R are missing makes the factorization R = P Q a difficult non-convex optimization problem [11]. Current MF techniques works by minimizing an error function that measures the factorization quality, and the most popular solutions are Alternating Least Squares (ALS) and Stochastic Gradient Descent (SGD). Both algorithms need several passes through the set of ratings to achieve this goal. ALS [9] alternates between keeping P and Q fixed. The idea is that, although both these values are unknown, when the item vectors are fixed, the system can recompute the user vectors by solving a least-squares problem (that can be solved optimally), and vice versa. SGD [10] works by taking steps proportional to the negative of the gradient of the error function. The term stochastic means that P and Q are updated, at each iteration, for each given training case by a small step, toward the average gradient descent.

Some recent works aimed at increasing the scalability of SGD [12,13,14], however the asymptotic cost of this technique makes it difficult to fit the timeliness requirements of real-world applications, especially when applied on large data sets. Furthermore, each update leads to non-local changes (for each observation the user vector increment is proportional to the item vector, and vice versa) which increase the difficulty (i.e. the communication costs) of distributed implementations.

Recently, new CF techniques have been proposed that consider the time dimension in ratings data. The main motivation behind these new approaches is that users taste change over time. Moreover, the user base, as well as item base, keep growing in the system. Traditional CF techniques don’t take into account this behavior and need to be periodically trained in order to be up-to-date with the latest information. Both memory-based and model-based approaches have been adapted to take temporal effects into consideration.

The most natural way to adapt neighborhood-based algorithms to temporal effects is to somehow give more relevance to recent observations, and less to past observations. This can be achieved using a series of techniques, most of which are based on either discrete time windows [15] or continuous decay functions [16, 17].

Matrix factorization algorithms have recently been adapted to cope with temporal effects. In [18] the SVD algorithm is extended to tackle temporal effects, using a combination of discrete time windows (for items) and continuous decay functions (for users). The idea proposed in [19] is to introduce time factors into the rating matrix, splitting the time in discrete windows.

One emerging trend in the Web 2.0 is that user’s interactions with the systems are becoming highly dynamic. It is therefore crucial for a CF algorithm operating in this environment to be capable of dynamically tracking users’ interests and providing very fast responses. In order to achieve such a goal, a straightforward strategy would be to adopt any existing CF algorithm and simply repeatedly rebuild the model using both old and new data. However most algorithms typically need a very lengthy training stage, and the computational complexity of this naive approach would not be affordable for applications requiring fast responses. It is therefore necessary to develop incremental algorithms that can efficiently adapt existing model using the new data. The algorithm described in [17] has an incremental and low complexity similarity computation, allowing the system to perform online updates. The possibility to update incrementally the model is an essential feature that a CF algorithm that copes with unbounded flow of data must possess. Several incremental solution have been proposed and evaluated [18, 19, 20, 21].

The main issue with online approaches is their short-term “memory”, i.e., since the updates based only on the most recent data point do not take into account past observations, the model quickly “forgets” them. Recently in [22] have been proposed a CF online learning algorithm that addresses this problem by keeping a representative sample of the data set in a reservoir and using only this sample plus the new observation for retraining. However, this research area is quite new, active and not solved, both for the algorithmic and the architectural aspects. The design of a distributed techniques aimed at providing scalable, low-latency solution for online rating aggregation and data stream processing is the main focus of the stereo project.