Recommending news articles is a challenging task due to the continuous changes in the set of available news articles and the contextdependent preferences of users. Traditional recommender approaches are optimized for analyzing static data sets. In news recommendation scenarios, characterized by continuous changes, high volume of messages, and tight time constraints, alternative approaches are needed. In this work we present a highly scalable recommender system optimized for the processing of streams. We evaluate the system in the CLEF NewsREEL challenge. Our system is built on Apache Spark enabling the distributed processing of recommendation requests ensuring the scalability of our approach. The evaluation of the implemented system shows that our approach is suitable for the news recommenation scenario and provides high-quality results while satisfying the tight time constraints.
In the last years, there has been an immense growth in the popularity of online newspapers. The huge amount of published news makes it di cult to nd the relevant articles. Therefore, services are needed supporting users in browsing the news and guiding users to the most interesting news taking into account the users preferences and the speci c context. In contrast to traditional \printed" newspapers, online news portals o er news much faster. Furthermore, online portal can adapt the visualization of news dynamically taking into consideration the most recent trends, the context and individual user preferences. The integrated recommender services have an important in uence on the news portals. Thus, the development and optimization of recommender systems for online news portals is a very active eld of research.
In order to support users in nding relevant items in large data collections, recommendation algorithms have been developed. Traditionally, these approaches are based on complex models computed on static data sets. In the eld of news recommendation, the sets of items change continuously. Therefore, the real-time adaptation of the applied models must be assured.
In this work we present an approach for the dynamic real-time creation of news recommendation models. We implement a most-popular algorithm that keeps track of the currently most frequently read news articles based on the Apache Spark framework1. Apache Spark enables the distributed processing and assures high scalability. We evaluate the algorithm in the CLEF NewsREEL challenge. This allows us to analyze our approach in two tasks. The Living Lab evaluation (NewsREEL Task 1) enables the recommender evaluation based on live user interaction; an Evaluation Lab (NewsREEL Task 2) focuses on the evaluation based on re-playing a data stream recorded in the living lab scenario. The evaluation data set has been provided by plista2, a company specialized in online advertisement. plista provides recommendations for most German news portals.
The remaining paper is structured as follows: Section 2 describes the scenario in detail and points out the speci c challenges. Related work is discussed in Section 3. In Section 4, we present our approach and explain the applied methods. The evaluation results are discussed in Section 5. Finally, a conclusion and an outlook to future work are given in Section 6. 2
In this Section we present the scenario in detail and explain the speci c challenges of the Living Lab news recommendation task. 2.1
The CLEF NewsREEL3 lab gives researchers the possibility to evaluate news
recommender algorithms under realistic conditions [
The analysis of the dataset shows that the number of interactions per user is small. This makes it di cult to adapt to individual user preferences since too little information about individual users is available. In addition, the user preferences are highly volatile and strongly in uenced by recent events and the time of the day. Based on this observation we focus on algorithms that analyze recent trends and the taste of the \crowd" for computing recommendations. Evaluation metrics The performance of a news recommendation system can be measured based on the Click-Through Rate (CTR) which is the ratio of users who click on a recommendation to the total number of o ered recommendations.
CT R =
#clicks #recommendations The evaluation scores are computed by plista. The results are visualized in an online portal for all participating recommendation systems on a weekly basis. 2.2
The provision of high quality news recommendations is a challenging task. Compared with traditional scenarios (focusing on recommending books or movies), the continuous changes in the set of users and items as well as the contextdependent relevance of items are di cult to handle. The short lifecycle of news items and fast changes in the user interest require a continuous adaption of the recommender models. Furthermore, the Living Lab evaluation in the CLEF NewsREEL de nes tight time constraints that must be ful lled also in load peak. This requires highly optimized data structures and algorithms scaling well with the number of requests per second. 3
In this Section we discuss existing recommender algorithms as well as news recommender systems and relevant frameworks. 3.1
The task of recommending is crucial in many di erent application scenarios.
Over the last decades several approaches have been suggested for computing
recommendations. We review the most commonly used approaches and discuss
the speci c strengths and weaknesses. We focus on collaborative ltering (CF)
algorithms, most-popular items methods, content-based algorithms as well as on
hybrid approaches combining two basic approaches [
Most Popular Items Most-popular Items algorithms suggest the most popular item in the community. The idea behind this popularity-based method is that items rated as relevant by a huge number of users are relevant for new users. The strengths of this approach are that no detailed knowledge about individual user preferences is required. Furthermore, these algorithms are able to adapt to new trends quickly. In addition, recommendations can be e ciently pre-computed since individual user preferences are not taken into account. The weaknesses of the most-popular items paradigm are that neither context nor individual user preferences are considered. This may lead to a reduced recommendation precision. Moreover, there is a high probability that the most popular items are already known to users.
User-based Collaborative Filtering User-based CF algorithms recommend items to users by determining users having a similar taste to the active user. The similarity is computed by analyzing the user behavior in the past. I.e., if user A and user B both assigned equal ratings to items c and d, users A and B are likely to have a similar taste. If user A rated e positively, a user-based CF recommender algorithm concludes that item e is a good suggestion for user B. Item-based Collaborative Filtering Item-based CF algorithms compute the similarity between items based on user feedback. Two items a and b are considered as similar if users tend to assign the same rating for a and b (\users who liked a also liked b"). If a user U rated item a positively, the system suggests an item similar but still unknown to U. The strength of this approach is that anonymous user feedback can be used and valuable explanation can be provided. Content-based Recommender Methods Content-based methods determine the items that should be recommended to the user by considering their ratings or consumption history. They try to nd the commonalities between the items in the user's history. Then these methods search for other items with similar characteristics. A requirement for this approach is that a certain amount of information on the user is indispensable.
Hybrid Recommender Approaches Hybrid approaches combine several of the presented recommender techniques. The combination helps to overcome the weaknesses of single algorithms and usually improves the recommendation precision in most scenarios. 3.2
Since news recommender system must be able to handle huge amount of messages, the scalability of online news recommender systems is an important requirement. In the NewsREEL challenge recommendation requests must be answered within 100 ms in all contexts and all load levels. This implies that a large amount of data must be processed within a short time period. Several frameworks have been developed tailored for the e cient processing of big data relying on the distributed processing, such as Apache Flink and Apache Spark. Spark seems to have a larger number of users and supporters as well as a more detailed documentation. Therefore, we decided to use the Apache Spark framework for our implementation. 3.3
Most existing recommender systems use either content-based or CF-based algorithms (cf. Sec. 2).
The content-based approach has been applied in a range of recommender
systems. Unlike CF methods, in its basic implementation it cannot take variability
between users into account. Carreira et al. [
Kim and Chan [9] describe an algorithm for creating user pro les that neither depends on initial ratings nor on the time users spent on an article. Their approach consists in constructing a cluster hierarchy from general to speci c interests for each user. Therefore, merely the set of articles visited by a user is needed. Our data analysis has revealed that a large number of persons reads only one article such that we have too little information at hand for this approach.
CF is the other approach that has been applied in a wide range of news
recommender systems. Konstan et al. [10] provide news recommendations based
on explicit user ratings. With this method, the user interests can be captured
reliably. The additional e ort for the users can be seen as critical disadvantage
of that approach. In the algorithm designed for Google News, Das et al. [
An example of a hybrid approach of content-based methods and CF is
described in [12]. The authors developed an algorithm for providing
recommendations on Google News. The system calculates a content-based score for each
article based on the user's genuine news interests. Therefore, the system analyzes
the user's click history taking into account the in uence of current news trends
at his location. This content-based score is then multiplied with the CF score
that is calculated as described in [
Most of the described content-based and CF algorithms depend on detailed user and item data not available in the analyzed NewsREEL scenario. The analysis of the NewsREEL data has shown that a large fraction of users has read only one article. The user data provided in NewsREEL seems to be noisy due to privacy issues. Given these restrictions, we decided to use a most-popular approach for recommending the news articles. We contribute to the research eld of news recommendation by developing a highly scalable recommendation system using a state-of-the-art parallelization framework. Our system yields accurate recommendations depending on very little user information. 4
Given the very sparse user information provided by our data set, we refrained from applying a CF algorithm. In order to avoid computational overhead, we decide implementing a simple but e ective most-popular approach. The recommendation strategy is applied separately for each of the three news domains and can optionally be re ned for the provided categories (\sub-domains") in each domain. In the NewsREEL setting, users are not asked to explicitly rate articles. We treat each user-item interaction (\impression", \click") as an indicator that the user is interested in the news item since the user proactively clicked on the news article. In the most-popular approach, the challenge is to determine the most read news items at high scale. As the amount of articles steadily increases, the model must be updated continuously. In our system, we make use of the MapReduce mechanism provided in Spark. MapReduce is an appropriate method for quickly determining the most popular articles as it allows us to count the number of clicks each article in the stream received in a highly parallelized way. We store the incoming user interactions in a ring bu er of a prede ned size. If an element (i.e. a user-article interaction) is added to the bu er, a MapReduce algorithm is run using Spark to count the number of received clicks for each article in order to update the current model. Due to concurrency issues, only one MapReduce phase runs on a bu er at a time. If the data stream is fast there might be interactions that are overwritten without being incorporated into the model. Hence, choosing a good bu er size is highly relevant for ensuring high-quality recommendations. 4.1
In this section, we present the architecture of the implemented system and discuss technical issues. Worker Nodes
Context
Management Map Reduce
Tasks
Recommender and Models
The API de ned in the NewsREEL Living Lab scenario de nes that a web server must be used for handling messages and requests. The integration of Spark into a web server is a challenging requirement, since the Spark Streaming API does not provide a native consumer. In order to not depend on third party software, we decided to handle the requests ourselves as shown in Fig. 1. This has the bene t that the implemented approach allows us to pre-process the requests right away rather than sending them through a third-party messaging system like Apache Kafka. The management component handles pre-processed requests from the web server, delegating the requests to the respective recommender. The recommender handles several MapReduce tasks that run through Spark. If the system runs on a standalone Spark cluster, the web server is available on the same machine as the cluster master while the MapReduce jobs are parallelized on the slave nodes.
To further scale with the high demand while having a stable system, incoming impressions are stored in an optimized queue of xed size following the rst-in- rst-out scheme. For each domain and category a separate queue exists containing the most recent items. The MapReduce jobs compiling the recommendation results are scheduled such that there is only one active job at a time for each queue. Every time the queues are altered in some way, the system makes sure that another job will be started to update the results. Hence, in times of high throughput, a small queue size can force some items to be overridden without being processed by a MapReduce job. The loss of precision that this behavior might cause is acceptable if more popular articles still dominate the sample of impressions contained in the queues. Another possibility of bypassing this problem is to provide a bigger cluster such that the MapReduce jobs nish in time to incorporate new results. If a smaller queue size is chosen the adaptation to new trends is enhanced while a bigger queue size can store more details of the stream and reduces precision loss.
We evaluate the recommender system both in the Living Lab and in the Evaluation Lab scenario. First we analyze the performance of our component in the Evaluation Lab scenario. This allows us simulating high message load on our system to test scalability and stability. Second we analyze the response rate of our system in the Living Lab scenario. 5.1
In this section we evaluate the system with the focus on scalability. The scalability is an important aspect in news recommender systems due to the huge number of messages and the high variance in the messages volume induced by speci c events. Figure 2 shows that the number of impressions recorded by our system can change signi cantly over time. The high amplitude in Figure 2 relates to several big transfers of soccer players. As the articles in the presented news domain are dominated by sports news, the increase in impressions related to this kind of special events seems reasonable.
To further assess the capabilities of the system, we evaluated the throughput under extreme circumstances. Figure 3 shows the response time histogram on a single machine with 1000 threads simultaneously requesting recommendations and sending impressions.
It can be seen that there are three peaks. The rst peak marks requests that are answered immediately. This case occurs if the incoming JSON-string is corrupted or required information is missing. The second peak represents requests that are cached while the third are normal responses that are handled by the management and MapReduce components. The mean response time is about 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 6 4 2 0 8 6 4 2 0 8 6 4 2 0 8 6 1 2 3 4 4 5 6 7 8 8 9 01 11 21 21 31
response time (ms) 330 ms and considerably larger than the minimum response time constraint of 100 ms. This can be explained by the fact that the environment resided on a single machine with maximized throughput. In a production system, the expected mean response time is narrowed accordingly because of the distribution of the system and better scalability with high parallelism and throughput.
We analyze how distributing the system over several machines (using the Spark framework mechanism) in uences the performance. We built a cluster that consists of a master and two slave nodes as shown in Figure 4. The master resides on a virtual machine with 2 CPU's and 2.9 GB RAM. The machine is located outside of the local network and also hosts the application with the web server. The two slaves are located within the local network and have 8 CPU's each and 16 or 32 GB RAM. On each slave node, we deployed 4 worker instances that occupied 2 CPU's and 1.7 GM RAM each. We strongly recommend deploying the cluster locally for a production use case. For research purposes, we wanted to evaluate the impact of higher network latencies within the cluster. This scenario may also be of interest if the cluster must be available locally with a low risk of failure while a third party hosts the virtual machines for computations.
For the evaluation we recorded the NewsREEL Living Lab messages in May 2016. The messages in this data set are sent from the local network to the remote master to incorporate network latencies.
In the rst evaluation only one slave node with four workers has been used. In this scenario we test the current setup and determine the response time distribution of the system. In the second evaluation both slave nodes and eight workers have been used. This scenario determines the in uence more nodes and workers have on the results. With more computational power in the scenario with more workers, the quality of the results and the number of jobs that nished increased.
Summarizing the evaluation results, we state that the API limits us to use a single webserver as an entry point for messages from the service. In order to respond in time in the Living Lab scenario, the webserver must reside on a machine with many CPU cores to compensate for higher demand. Using more
Application and Webserver
Local
Master
Cluster Sender
Slave 1
Slave 2 slave nodes via the Spark frameworks enables us to improve recommendation quality while ensuring a reliable response rate of our system. 5.2
For the Evaluation Lab a data record of one week in the period between 7 March and 13 March 2016 is used. This time period has been selected because in this timeframe the Living Lab data stream provided a reliably high volume of data.
Kille et al. [8] introduced an o ine evaluation approach that we applied for the presented system. A stream was replayed which was recorded in a Living Lab setting. The message order is preserved. In contrast to the Living Lab setting the evaluation metric is based on future user impressions. An impression represents the evens that a user accesses a news article, not necessarily by clicking on a
16,924% 309,203%4 recommendation. A recommendation for a user is handled as correct in case the user reads the recommended article within a 5 minutes time window after the request. The impression based the o ine Click-Through Rate (CT Ro ine) is calculated in the following way.
CT Ro ine = #A #S Multiset A represents the recommendations handled as correct and multiset S represents all recommendations, which were given by the algorithm, in the evaluation period.
In the evaluation process three most popular algorithms, labeled with MostPopular300, MostPopular100 and CategoryMP100, have been deployed on a standalone local Spark cluster running on a single machine. The number in the label describes the size of the operation queue which is used by the algorithm. The replay of the data record is done on the same system. In reference to Figure 5 a data record analysis shows that the domain with ID 35774 is dominating the number of recommendation requests. Hence, the evaluation results are based on an analysis of the impression and requests related to domain 35774. The results are shown in Table 1 and indicate that all three algorithms signi cantly exceed the CT Ro ine performance of the baseline. This veri es that the evaluated algorithms generate adequate recommendations. 5.3
The implemented system has been evaluated on a single machine in the Living
Lab scenario [
In this paper we present a recommender system implementing a most popular strategy. Our system counts the number of impressions for the most recently read articles and suggests the currently most read news articles to the users. The recommender is based on the idea that articles interesting for many readers are also relevant for new users. The high requirements with respect to scalability and response time we address by building our recommender system on Apache Spark. The use of Apache Spark enables us running the recommender as a distributed system in a cluster ensuring the scalability of the approach. We have evaluated the system in a Living Lab and Evaluation Lab scenario. The Living Lab evaluation shows that our recommender system reliably reaches a good CTR. In the Evaluation Lab we showed that the system can handle huge data streams e ciently.
Future Work In the future we plan to evaluate additional recommendation models in order to further improve the CTR. Scaling the cluster horizontally makes it possible to use more elaborate algorithms from the Spark machine learning library while corresponding to the strict time constraints.
The research leading to these results was performed in the CrowdRec project, which has received funding from the European Union Seventh Framework Programme FP7/2007-2013 under grant agreement Nr. 610594. 8. B. Kille, A. Lommatzsch, G. Gebremeskel, F. Hopfgartner, M. Larson, J. Seiler, D. Malagoli, A. Sereny, T. Brodt, and A. de Vries. Overview of NewsREEL'16: Multi-dimensional Evaluation of Real-Time Stream- Recommendation Algorithms. In N. Fuhr, P. Quaresma, B. Larsen, T. Goncalves, K. Balog, C. Macdonald, L. Cappellato, and N. Ferro, editors, Experimental IR Meets Multilinguality, Multimodality, and Interaction 7th Intl. Conf. of the CLEF Association, CLEF 2016, Evora, Portugal, September 5-8, 2016., LNCS 9822. Springer, 2016. 9. H. R. Kim and P. K. Chan. Learning implicit user interest hierarchy for context in personalization. In IUI '03: Proceedings of the 8th international conference on Intelligent user interfaces, pages 101{108, New York, NY, USA, 2003. ACM Press. 10. J. A. Konstan, B. N. Miller, D. Maltz, J. L. Herlocker, L. R. Gordon, and J. Riedl.
Grouplens: Applying collaborative ltering to Usenet news. Communications of the ACM, 40(3):77{87, 1997. 11. L. Li, D.-D. Wang, S.-Z. Zhu, and T. Li. Personalized news recommendation: A review and an experimental investigation. Journal of Computer Science and Technology, 26(5):754{766, 2011. 12. J. Liu, P. Dolan, and E. R. Pedersen. Personalized news recommendation based on click behavior. In Proceedings of the 15th International Conference on Intelligent User Interfaces, IUI '10, pages 31{40, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-515-4.