Antoine Boutet
email: antoine.boutet@inria.fr

Davide Frey
email: davide.frey@inria.fr

Rachid Guerraoui
email: rachid.guerraoui@epfl.ch

Anne-Marie Kermarrec
email: anne-marie.kermarrec@inria.fr

Rhicheek Patra
email: rhicheek.patra@epfl.ch

HyRec: Leveraging Browsers for Scalable Recommenders

Keywords: H.3.3 [Information Search and Retrieval]: Information filtering, H.3.5 [Online Information Services]: Web-based services, K.6.4 [System Management]: Centralization/decentralization Personalization, Collaborative Filtering, Recommendation Systems

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Personalization has become an essential tool to navigate the wealth of information available on the Internet. Particularly popular now are recommendation systems which provide users with personalized content, based on their past behavior and on that of similar users. These systems have been successfully applied by major online retailers such as Amazon to propose new items to their cus-tomers. Social networks, such as Facebook, exploit them to suggest friends to users and to filter the content displayed on their feeds, while Google or Yahoo! use them to provide personalized news to users.

Yet, the need to personalize content is no longer an exclusive requirement of large companies. Personalization is arguably crucial for every web-content editor, including relatively small ones. A very typical example is that of VideoJeux.Com1 , a relatively small French online video-game magazine employing 20 people only, while gathering 3 million registered users (responsible for only 20% of the traffic: the rest being generated by unregistered ones who comment and discuss published content). The site of the company, visited 45 million times per month, enables access to 6, 000 discussion forums, which in turn generate up to 300, 000 messages per day. In many cases, the amount of information sometimes over-floods specialized users interested in specific games, who finally unregister. Clearly, the number of companies in similar situations is growing and all would greatly benefit from a personalization scheme providing users with recommendations about what they would most likely be interested in. However, state-of-the-art personalization solutions still represent a significant investment in terms of computing power and money.

The motivation of our work is to explore solutions that can "democratize personalization" by making it accessible to any contentprovider company, without requiring huge investments. In this paper, we introduce HyRec,amiddleware hybrid architecture capable of providing a cost-effective personalization platform to webcontent editors. Instead of scaling either through larger and larger recommendation back-end servers, or through fully decentralized solutions that rely solely on clients, HyRec delegates expensive computation tasks to users' web browsers while, at the same time, retaining on the server side the system's management tasks and the maintenance of the graph reflecting the relationships between user profiles.

HyRec implements a user-based collaborative-filtering scheme (CF): it predicts the interests of a user by collecting preferences or taste information from many other users (collaborating) [START_REF] Ekstrand | Collaborative Filtering Recommender Systems[END_REF]. CF is content agnostic and represents a natural opportunity for decentralizing recommendation tasks on user machines. More specifically, HyRec adopts a k-nearest-neighbor (KNN) strategy, which consists in computing the k nearest neighbors according to a given similarity metric, and identifying the items to recommend from this set of neighbors [START_REF] Su | A survey of collaborative filtering techniques[END_REF]. The challenge is to cope with a large number of users and items. Traditional centralized recommendation architectures achieve this by computing neighborhood information offline and exploiting elastic cloud platforms to massively parallelize the recommendation jobs on a large number of nodes [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF][START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF]. Yet, offline computation is less effective when new content is continuously added: forcing periodic re-computations induces significant costs [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF][START_REF] Linden | com recommendations: item-to-item collaborative filtering[END_REF][START_REF] Meisner | Power management of online data-intensive services[END_REF].

HyRec's architecture avoids the need to process the entire sets of users and items by means of a sampling-based approach inspired by epidemic (gossip-based) computing [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF][START_REF] Bertier | The gossple anonymous social network[END_REF], and successfully used in state of the art KNN graph construction [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] as well as query processing [START_REF] Agarwal | Blinkdb: queries with bounded errors and bounded response times on very large data[END_REF].

The computation of the personalization operations of a user are performed transparently by the browser on the user's machine (which we sometimes simply call "the user" or "the client"). The HyRec server provides each user's browser with a sample set of profiles of other users (candidate set). Every browser then computes its user's KNN and most popular items based on this sample. The server uses, in turn, the user's new neighbors to compute the next sample. This iterative process implements a feedback mechanism that keeps improving the quality of the selected neighbors and leads them to converge very quickly to those that could have been computed using global knowledge. This is achieved without the need for HyRec to reveal the identity of any user to other users: the user/profile association is hidden through an anonymous mapping: periodically, the identifiers of the items and the users in the candidate sets are anonymously shuffled.

We fully implemented HyRec and its code is available [START_REF] Hyrec | [END_REF]. We also extensively evaluated it in the context of two use cases: Digg, a personalized feed, and MovieLens, a movie recommender. We used real traces in both cases. We compared HyRec with solutions based on a centralized infrastructure as well as with a fully decentralized one. Our results show that the quality of the KNN approximation provided by HyRec is within 10% of the optimum for MovieLens. As the convergence of the KNN graph is driven by user activity, users who are frequently online benefit from a better approximation than users who are rarely online. We show that the reactiveness of HyRec in computing and refining the KNN graph during the activity of online users drastically improves recommendation quality with respect to solutions that use offline clustering, which may update this graph too late to provide useful recommendations.

HyRec reduces the server's computational cost by a factor ranging from 1.4 to 2. We show that, as the scale of the system increases, its ability to serve clients is much higher than that of a centralized approach (100-fold improvement). By computing KNN selection at the edge of the network on user machines, HyRec inherently reduces the operational costs incurred by the content provider. With our largest case study, HyRec yields a cost reduction for the content provider of nearly 50% with respect to a centralized solution. We show that the impact of HyRec on user machines is negligible, compared to a fully decentralized (P2P) solution. In the case of our Digg dataset for instance, a single user machine transmits around 24MB with the P2P approach, and only 8kB with HyRec. We also show that HyRec can exploit clients with small mobile devices without impacting user activities.

The rest of the paper is organized as follows. In Section 2 we introduce some background on collaborative filtering and recommender architectures. Section 3 and Section 4 present the design and implementation of HyRec. Our extensive evaluation of HyRec follows in Section 5. Section 6 concludes the paper.

BACKGROUND AND RELATED WORK

Before presenting HyRec, we provide some background on userbased collaborative filtering (CF) systems. We also recall the principles underlying centralized and decentralized CF recommendation systems (or simply recommenders) and motivate the very notion of a hybrid architecture.

Collaborative filtering

While content-based recommenders leverage content similarities between items, user-based collaborative filtering (CF in the following) focuses mainly on users [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF]. CF recommenders build neighborhoods of users based on their interests in similar (e.g. overlapping) sets of items. Due to its content-agnostic nature, CF has now been adopted in a wide range of settings [START_REF] Ekstrand | Collaborative Filtering Recommender Systems[END_REF].

Notations. We consider a set of users U = u1,u2,...,uN and a set of items I = i1,i2,...,iM . Each user u 2 U has a profile Pu = <u,i,v>, collecting her opinions on the items she has been exposed to, where u is a user, i an item, and v the score value representing the opinion of user u on i. For the sake of simplicity, we only consider binary ratings indicating whether a user liked or disliked an item after being exposed to it. This rating can be easily extended to the non-binary case [START_REF] Resnick | Grouplens: an open architecture for collaborative filtering of netnews[END_REF].

Two steps are typically involved when a recommender provides a user with a set of items R ✓ I: neighbor selection and item recommendation. Su) where Pu is the profile of the user u and Su is a candidate set for user u 1: var similarity[]; 2: for all uid : user in Su do 3: similarity[uid]=score(Pu, Su[uid].getP rof ile()); 4: end for 5: Nu = subList(k, sort(similarity)); 6: return: Nu, the k users with the highest similarity;

Algorithm 1 KNN selection: γ(Pu,
Neighbor selection. Neighbor selection consists in computing, for each user u, the (k) most similar users (referred to as KNN, k nearest neighbors, in the rest of the paper), with respect to a given similarity metric: we use cosine similarity [START_REF] Ekstrand | Collaborative Filtering Recommender Systems[END_REF] in this paper, but any other metric could be used. A brute force KNN computation has a complexity of O(N 2 ) and designing low-complexity computations remains an open problem. We use a sampling-based approach to reduce drastically the dimension of the problem while achieving accurate results. The approach proceeds by successive approximations. At each iteration (Algorithm 1), it identifies a set of candidate users starting from the current KNN approximation, Nu. Then it computes the similarity between u's profile and that of each user in the candidate set and updates the KNN approximation by retaining the best candidates. This sampling-based approach is also a good candidate for decentralization as it does not require any global knowledge about the system. Indeed it is used in both centralized [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] and decentralized [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Baraglia | A peer-to-peer recommender system for self-emerging user communities based on gossip overlays[END_REF] recommenders although the details of the computation of the candidate set may differ. Item recommendation. A user-based recommender makes recommendations based on the user profiles identified during the KNNselection phase (Algorithm 2). In our context, we consider a sim-ple scheme: The system recommends to a user u the r items that are most popular among the profiles in the candidate set identified when computing the KNN of u [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF].

The presence of new users (i.e with empty profiles) and new items (i.e. without ratings) leads to the so-called cold-start issue. Solutions to this problem typically rely on application-specific techniques such as content-based recommendation and are therefore out of the scope of this paper. Similarly, for the sake of simplicity, we do not consider the retrieval of recommended items and we assume that items are hosted somewhere else.

Centralized architecture

A typical recommender follows a client-server interaction model (Figure 1), namely a centralized architecture. The server maintains two global data structures: A Profile Table, recording the profiles of all the users in the system and the KNN Table containing the k nearest neighbors of each user. Users interact with a web browser, which in turn communicates with the server to update the profiles, fill the KNN tables, and compute the recommendations.

In this setting, the server performs all computation tasks. These include running KNN selection and item recommendation for all users. Due to its high computational cost, the neighbor selection is typically performed periodically offline on back-end servers, while item-recommendation is achieved in real time. Clearly, the load on the server also depends on the number of concurrent (online) users. The web server, application logic, recommendation subsystem, and associated databases may leverage distribution, for example by delegating computation-and data-intensive recommendation tasks to a data center using cloud-based solutions like in Google News [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF]. Yet, all active components remain under the responsibility of the website owner.

One of the main challenges underlying centralized CF architectures is scalability. This is particularly true for websites that enable users to generate content. Dimension reduction and algorithmic optimizations [START_REF] Grover | Extending map-reduce for efficient predicate-based sampling[END_REF][START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF], or sample-based approaches [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF][START_REF] Ene | Fast clustering using mapreduce[END_REF][START_REF] Diaz-Aviles | Real-time top-n recommendation in social streams[END_REF], partially tackle the problem. Yet they do not remove the need to increase computational resources with the number of users and items [START_REF] Jia | Bi-level locality sensitive hashing for k-nearest neighbor computation[END_REF][START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF][START_REF] Brand | Fast online svd revisions for lightweight recommender systems[END_REF]. Even with massive (map-reduce) parallelization [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF] on multicore [START_REF] Ranger | Evaluating mapreduce for multi-core and multiprocessor systems[END_REF][START_REF] Mao | Optimizing mapreduce for multicore architectures[END_REF] or elastic cloud architectures [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF], CF remains expensive in terms of both hardware and energy consumption [START_REF] Chen | Energy efficiency for large-scale mapreduce workloads with significant interactive analysis[END_REF][START_REF] Meisner | Power management of online data-intensive services[END_REF].

Decentralized architecture

A radical way to address scalability is through a significant departure from centralized (cloud-based) architectures, namely through fully distributed solutions [START_REF] Zeilemaker | Tribler: P2p media search and sharing[END_REF][START_REF] Rosaci | Muaddib: A distributed recommender system supporting device adaptivity[END_REF][START_REF] Ardissono | A multi-agent infrastructure for developing personalized web-based systems[END_REF][START_REF] Miller | Pocketlens: toward a personal recommender system[END_REF][START_REF] Zhang | On building and updating distributed lsi for p2p systems[END_REF]. A fully decentralized architecture, e.g. [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF][START_REF] Baraglia | A peer-to-peer recommender system for self-emerging user communities based on gossip overlays[END_REF], builds an overlay network comprising all user machines, typically resembling a uniform random graph topology [START_REF] Jelasity | Gossip-based peer sampling[END_REF]. Users can join and leave the system at any time, e.g. due to machine failures or voluntary disconnections. No user has global knowledge of the system. Instead, each maintains her own profile, her local KNN, and profile tables. This allows a user to compute her own recommendations without further interaction with other users, or a server.

Decentralized solutions exploit a sampling protocol similar to the one in Algorithm 1. At each iteration, each user, u, exchanges information with one of the users, say v, in her current KNN approximation. Users u and v exchange their k nearest neighbors (along with the associated profiles) and each of them merges it with an additional random sample obtaining a candidate set. Each of them then computes her similarity with each user in her candidate set and selects the most similar ones (see Figure 1 and Algorithm 1) to update her KNN approximation. This process converges in a few cycles (e.g. 10 to 20 in a 100.000 node system [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF]).

The absence of a server makes it possible to fully distribute KNN selection and item recommendation. However, fully decentralized solutions-like the one we implemented and compare with in Section 5.6-face important deployment challenges. They require users to install specific software that must manage their on/off-line patterns, while taking care of synchronization between multiple devices that may not be online at the same time. Moreover, they require substantial complexity to deal with NAT devices and firewalls. These limitations, combined with the inherent scalability of decentralized solutions, provide a strong motivation for a hybrid approach like ours.

Towards a hybrid architecture

A hybrid approach combines a centralized entity that coordinates tasks and manages the graph of relationships between users with processes that run on user machines to perform computationally intensive tasks. The central entity can effectively manage dynamic connections and disconnections of users, while retaining the main scalability advantages of decentralized solutions. Unlike [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF], HyRec allows clients to have offline users within their KNN, thus leveraging clients that are not concurrently online. Moreover, HyRec makes it possible to compute similarities with all the 2-hop neighbors at once, leading to faster convergence.

Hybrid approaches have already proved successful in various contexts. SETI@home [START_REF]Seti@home[END_REF] leveraged the machines of volunteers to analyze radio-telescope data whereas Weka [START_REF] Khoussainov | Grid-enabled weka: A toolkit for machine learning on the grid[END_REF] does something similar for data mining. A distributed Weka requires either a grid hosted by the content-provider, or an application server on the clients. In addition, Weka is oriented towards data analysis and does not provide a real-time personalization system. TiVo [START_REF] Ali | Tivo: making show recommendations using a distributed collaborative filtering architecture[END_REF] proposed a hybrid recommendation architecture similar to ours but with several important differences. First, it considers an item-based CF system. Second, it does not completely decentralize the personalization process. TiVo only offloads the computation of item recommendation scores to clients. The computation of the correlations between items is achieved on the server side. Since the latter operation is extremely expensive, TiVo's server only computes new correlations every two weeks, while its clients identify new recommendations once a day. This makes TiVo unsuitable for dynamic websites dealing in real time with continuous streams of items. As we explain below, HyRec addresses this limitation by delegating the entire filtering process to clients. It is to our knowledge the first system capable of doing so on any user-based CF platform.

HYREC

As we pointed out, HyRec lies between cheap, but complex-toimplement, hard-to-maintain, decentralized solutions, and efficient, but potentially costly, centralized designs. It leverages the locality of the computation tasks involved in user-based CF schemes.

The bottom of Figure 1 shows HyRec's hybrid architecture and its interaction pattern. The server delegates both KNN selection and item recommendation to user's web browsers using a samplingbased approach. Consider a user, u, that accesses a web page with recommendations. The server first updates u's profile in its global data structure. Then, it identifies a personalized candidate set for u, containing the profiles of candidate users for the next KNN iteration, and sends it to the browser, which executes a piece of JavaScript code attached to the web page. This code computes the recommended items, it performs the similarity computations between the local profile and the ones in the candidate set, and sends the results to the server. In the following, we detail this process by focusing on each component of the architecture.

HyRec server

The server is in charge of (i) orchestrating the decentralization and (ii) maintaining the global data structures, a profile table and a KNN table. Each entry in the Profile and the KNN tables associates the identifier of each user respectively with her own profile and with those of the users in her current KNN approximation.

The server decomposes the recommendation process into personalization jobs that run on client-side widgets in the browsers of (connected) users. A personalization job essentially consists of a message containing the candidate set that allows the client to perform (i) KNN selection, and (ii) item recommendation by executing JavaScript code. In the following, we describe the two components of the server depicted in Figure 1: the Sampler and the Personalization orchestrator.

Sampler

HyRec relies on the sampling approach outlined in Algorithm 1 to associate each user with her k nearest neighbors. This local and iterative algorithm, inspired from epidemic clustering protocols [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF][START_REF] Bertier | The gossple anonymous social network[END_REF], leads to an online KNN-selection process, unlike the periodic one used in centralized architectures. This makes the system more reactive to dynamic interests.

The sampler participates in each iteration of the sampling algorithm and is responsible for preparing the candidate set (or sample). This consists of a small (with respect to the total number of users) set of candidate users, from which the client selects its next k nearest neighbors. Let Nu be a set containing the current approximation of the k nearest neighbors of u (k is a system parameter ranging from ten to a few tens of nodes). The sampler samples a candidate set Su(t) for a user u at time t by aggregating three sets: (i) the current approximation of u's KNN, Nu, (ii) the current KNN of the users in Nu, and (iii) k random users. Because these sets may contain duplicate entries (more and more as the KNN tables converge), the size of the sample is  2k + k 2 . As the neighborhood of u, Nu, converges towards the ideal one (N * u ), the candidate set tends to get smaller and smaller as shown in Section 5.2.

By constraining the size of the candidate set, HyRec's samplingbased approach not only limits computational cost, but also network traffic, while preserving recommendation quality as we show in our experiments. Research on epidemic [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF] and k-nearestneighbor graph construction [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] protocols show that the process converges very rapidly even in very large networks. Using u's neighbors and their neighbors provides the client with a set of candidates that are likely to have a high similarity with u. Adding random users to the sample prevents this search from getting stuck into a local optimum. More precisely, this guarantees that the process will eventually converge in the absence of profile changes by recording the user's k-nearest neighbors in the set Nu, so that limt→∞ Nu -N * u =0 , where N * u is the optimal set (i.e. containing the k most similar users). When profiles do change, which happens frequently in the targeted applications (e.g. news feed), the process provides each user with a close approximation of her current optimal neighbors.

Personalization orchestrator

The personalization orchestrator manages the interaction with the browsers. Once a user u accesses the server, (Arrow 1 in Figure 1), the orchestrator retrieves a candidate set, parametrized by k from the sampler and builds a personalization job. The personalization job for u consists of a message that includes u's profile and the profiles of all the candidates returned by the sampler (Arrow 2 in Figure 1). Finally, the orchestrator sends the personalization jobs, and updates the global data structures with the results of the KNNselection iteration. Figure 2 illustrates the interactions between the clients and the server in HyRec as well as in a centralized approach. Clearly, sharing profiles among users may compromise their privacy. However, HyRec hides the user/profile association through an anonymous mapping that associates identifiers with users and items. HyRec periodically changes these identifiers to prevent curious users from determining which user corresponds to which profile in the received candidate set. As we discuss in Section 6, this mechanism does not suffice in the case of sensitive information (e.g., medical data) if cross-checking items is possible.

HyRec client

In HyRec, users interact with the recommender system through a web interface. The client side of HyRec consists of a javascript widget, running in a web browser. This widget serves as a web container that interacts with the server's web API. The HyRec widget sends requests to the server whenever the user, u, requires some recommendations. The server replies by providing a personalization job containing a candidate set. Upon receiving the job, the widget (i) computes u's recommended items and (ii) runs an iteration of the KNN-selection algorithm. Thanks to HyRec's hybrid architecture, the widget does not need to maintain any local data structure: it receives the necessary information from the server and forgets it after displaying recommendations and sending the new KNN to the server.

Recommendation

Given the candidate set, Su, and u's profile, Pu, the widget computes u's personalized recommendations as Ru = α(Su,Pu), where α(Su,Pu) returns the identifiers of the r most popular items among those that appear in the profiles in Su, but not in Pu. These consist of the most popular items in Su to which u has not yet been exposed.

As explained in Section 3.1, the candidate set contains the profiles of u's neighbors, u's two-hop neighbors, and k random users. By taking into account the items liked by the (one-and two-hop) neighbors, item recommendation exploits the opinions of similar users. By also taking into account items from the profile of random users, it also includes some popular items that may improve the serendipity of recommendations.

In a real application, once the item to be recommended have been identified, they might need to be retrieved from a web server to be displayed in a web page. We omit the process of retrieving the actual content of these items since this is application-dependent.

KNN selection

The client also updates the user's k-nearest neighbors. To achieve this, the KNN algorithm (Algorithm 1) computes the similarity between u's profile, Pu, and each of the profiles of the users in the candidate set, Su. It then retains the users that exhibit the highest similarity values as u's new neighbors, Nu = γ(Pu, Su), where γ(Pu,Su) denotes the k users from Su whose profiles are most similar to Pu according to a given similarity metric (here the cosine similarity). This data is sent back to the server to update the KNN table on the server (Arrow 3 in Figure 1).

HYREC IMPLEMENTATION

Our implementation of HyRec consists of a set of server-side modules and a client-side widget.

J2EE Servlets

Each component of the server consists of a J2EE servlet. These servlets come in two flavors: either as stand-alone components that can be run in different web servers, or bundled all together with a version of Jetty [START_REF] Jetty | [END_REF], a lightweight web server. Integrating the servlets into different customized web servers allows content providers to deploy our architecture on multiple hosts, thereby balancing the load associated with the various recommendation tasks (e.g. network load balancing). Bundling them with a Jetty instance makes it easy for content providers to deploy our solution into their existing web architectures.

Javascript Widget

The HyRec widget consists of a piece of JavaScript code attached to web pages, and can be executed without the need of special plugins. The widget's code use the jQuery implementation [10]. It identifies users through a cookie, collects user activities, runs KNN selection and item recommendation, manages the retrieval of the recommended items and displays them. All exchanges between the server and the widgets are formatted into JSON messages and compressed on the fly by the server using gzip (browsers are natively able to decompress messages). We use the Jackson implementation [START_REF][END_REF] to serialize JAVA objects to JSON message.

The use of JavaScript makes the operation of HyRec totally transparent to users thanks to the asynchronous nature of the AJAX model, which dissociates the display of a web page from the actions (i.e. javascript files, network communication) associated with it. Consider a web page that contains the HyRec widget: the browser will first display the web-page content, then it will asynchronously execute the personalization job and display the recommendation once all computations have completed.

Web API

The widget communicates with the HyRec server through the web API described in Table 1. The use of a public web API not only provides a simple way to implement our widget but also achieves authentication and makes it possible for content providers to build their own widgets that interact with HyRec. To develop a new widget, one simply needs to make the right API calls and tune Web API https://HyRec/online/?uid=uid Client request https://HyRec/neighbors/?uid=uid&id0=fid0&id1=fid1&... Update KNN selection Customizable interfaces and methods interface Sampler{...} Java interface on server side to define the sampling strategy setSimilarity();

Customizable method on widget to determine the similarity metric for the neighbors selection setRecommendedItems(); Customizable method on widget to determine the selected items to recommend Table 1: Web API and main tools to customize HyRec.

the Javascript file associated with the HyRec widget. The content provider can tune the parts of the widget that process personalization jobs and collect user activities. For example, our implementation uses the cosine similarity metric and the most popular itemrecommendation algorithm, but content providers can define new similarity metrics as well specify a new algorithm for item recommendation.

The current version of HyRec also integrates interfaces to customize parts of its behavior on the server-side. For example, content providers can control the sampling process and the size of user profiles, depending on the application, by means of the Sampler interface in Table 1. Similarly, they can include new fields in user profiles in the corresponding JSON messages returned by the API calls. All these settings are entirely transparent to end users.

EVALUATION

In this section, we show that HyRec meets ours goals: providing good-quality recommendations, reducing cost, and improving the scalability of the server as compared to a centralized approach; and this, without impacting the client, be it running on a smartphone or a laptop. We also show that HyRec uses less bandwidth than a decentralized recommender, besides not requiring custom software on user machines. We start with a description of the experimental setup. We then study KNN selection, recommendation quality, their impact on cost, and we evaluate the performance of HyRec's server and client in comparison with alternatives.

Experimental setup

Platform

We consider a single server hosting all components (front and backend) and assume that the database is entirely stored in memory. In practice, several machines can be used to implement each component separately to sustain the load at the network level. Yet, this does not affect the outcome of our experiments. We use a Pow-erEdges 2950 III, Bi Quad Core 2.5GHz, with 32 GB of memory and Gigabit Ethernet, to evaluate the server. To evaluate the client, we use both a Dell laptop latitude E4310, Bi Quad Core 2.67GHz with 4 GB of memory and Gigabit Ethernet under Linux Ubuntu, and a Wiko Cink King smartphone with Wi-Fi access running an Android system.

Datasets

We use real traces from a movie recommender based on the Movie-Lens (ML) workload [START_REF] Movielens | [END_REF] and from Digg [4], a social news web site. The ML dataset consists of movie-rating data collected through the ML recommender web site during a 7-month period and is often used to evaluate recommenders [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF]. For the sake of simplicity, we project ML ratings into binary ratings as follows: for each item (movie) in a user profile, we set the rating to 1 (liked) if the initial rating of the user for that item is above the average rating of the user across all her items, and to 0 (disliked) otherwise. We use the three available versions of this dataset, varying in their number of users, to evaluate the quality of recommendation in HyRec. The Digg dataset allows us to consider an even more dynamic setting. Digg is a social news web site to discover and share content where the value of a piece of news is collectively determined. We collected traces from Digg for almost 60, 000 users and more than 7, 500 items over 2 weeks in 2010. This dataset contains all observed users in the specified period. Table 2 summarizes the workload. The average number of ratings per user for the Digg dataset is significantly smaller than for the ML datasets.

Dataset

Competitors

We compare the performance of HyRec with that of several alternatives to highlight the benefits and limitations of our approach. The alternatives include both centralized and completely decentralized approaches. For centralized approaches, we distinguish two major families. Offline solutions perform KNN selection periodically on a back-end server, while they compute recommendations on demand on a front-end. Online solutions perform both KNN selection and item recommendation on demand on the front-end.

Metrics

View Similarity. To measure the effectiveness of HyRec in finding the nearest neighbors in term of interest, we compute the average profile similarity between a user and her neighbors, referred to as view similarity in the following. We obtain an upper bound on this view similarity by considering neighbors computed with global knowledge. We refer to this upper bound as the ideal KNN in the rest of the evaluation. Recommendation Quality. To measure and compare recommendation quality, we adopt the same approach as in [START_REF] Levandoski | Lars: A location-aware recommender system[END_REF]. We split each dataset into a training and a test set according to time. The training set contains the first 80% of the ratings while the test set contains the remaining 20%. For each positive rating (liked item), r, in the 20%, the associated user requests a set of n recommendations, <. The recommendation-quality metric counts the number of positive ratings for which the < set contains the corresponding item: the higher the better. If a positive rating represents a movie the user liked, this metric counts the number of recommendations that contain movies that the user is known to like. System Metrics. To evaluate the performance of HyRec's hybrid architecture, we measure execution time on both the HyRec server and the HyRec client. We also measure the bandwidth consumed during their exchanges. Finally, we measure the impact of HyRec on other applications running on a client machine as well as the impact of the load on the client machine on HyRec's operation.

KNN selection quality

To evaluate the quality of the KNN selection provided by HyRec, we replay the rating activity of each user over time. When a user rates an item in the workload, the client sends a request to the server, triggering the computation of recommendations. We compare HyRec with the upper bound provided by the ideal KNN.

Figure 3 displays the average view similarity over all the users in the ML1 dataset as a function of time. Users start with empty profiles. As time elapses, they replay the ratings in the dataset, thereby increasing the average view similarity over time. The plot compares the results obtained by HyRec with those obtained by Offline Ideal. This consists of an offline protocol that computes the ideal KNN once a week. The period of one week allows us to identify a step-like behavior in the offline approach. This is because in offline protocols the neighbors remain fixed between two periodic computations and thus cannot follow the dynamics of user interests. A typical period in existing recommenders is in the order of 24h. Such a shorter period would make the steps thinner but it would not lead to faster convergence. Indeed, the upper bound on view similarity can be obtained by connecting the top-left corners of the steps in the offline-ideal curve on Figure 3. This upper bound corresponds to an online protocol that computes the ideal KNN for each recommendation. While interesting as a baseline, such a protocol is inapplicable due to its huge response times as we show in Section 5.5. Overall, Figure 3 shows that HyRec effectively approximates this upper bound. For a neighborhood size of k =10, HyRec's average view similarity remains within 20% of that of the ideal KNN at the end of the experiment. The curve for k =2 0shows the impact of the neighborhood size: larger values of k result in larger candidate sets that converge faster to the nearest neighbors.

HyRec is an online protocol in the sense that it runs KNN selection as a reaction to user requests. The timing of such requests follows the information available in the data trace. As a term of comparison, we also consider a variant (IR=7) that bounds the interrequest time (i.e. the interval between two requests of the same client) to one week. Results show that the quality of KNN selection drastically improves according to the activity of users: more frequent user activity results in better view quality. An inter-request period of one week for k =10is enough to bring HyRec's approximation within 10% of the upper bound at the end of the experiment.

To further analyze the impact of user activity on the KNN pro- vided by HyRec, we plot the view similarity of each user as a percentage of her ideal view similarity (i.e. that of the ideal KNN) after replaying all the dataset. Figure 4 shows the results as a function of profile size. In our experimental setting, larger profiles imply more recommendation requests and thus more KNN iterations. Results clearly show the correlation between the number of iterations and the quality of KNN selection. More active users benefit from better KNN selection. The plot also shows that the vast majority of users have view-similarity ratios above 70%.

The iterative approach of HyRec refines its KNN selection over time. As the KNN of each user converge, the average size of the candidate set tends to decrease as each candidate is more likely to be a neighbor. Figure 5 depicts the average candidate-set size on the entire ML1 workload as a function of time for different values of k. We observe that the candidate-set size quickly converges to a stable value. For instance, for k =1 0 , its value quickly converges to around 55 instead of the upper bound of 120. The small fluctuations in the curve result from the continuous arrival of new users, who start with large candidate sets.

Recommendation quality

The recommendation process leverages KNN selection to identify the items to recommend as explained in Section 2. To evaluate this, Figure 6 plots the recommendation-quality metric against the number of recommendations provided in response to each client request. As described in Section 5.1, recommendation quality counts the number of recommendations that refer to positive ratings in the testing set [START_REF] Levandoski | Lars: A location-aware recommender system[END_REF]. For a fixed number of recommendations (x coordinate in the plot), higher recommendation quality implies both higher precision and higher recall [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF].

Figure 6 compares HyRec with systems based on ideal KNN (both offline and online). The recommendation quality of offline approaches drastically changes according to the period of offline KNN selection (parameter p on Figure 6). The online-ideal solution, on the other hand, provides an upper bound on recommendation performance by computing the ideal KNN before providing each recommendation.

HyRec yields an up-to-12% improvement in recommendation quality with respect to the offline-ideal approach even when this runs with a period of 24 hours, which is already more costly than HyRec as we show in Section 5.4. It also provides better performance than offline ideal with a period of 1 hour and scores only 13% below the upper bound provided by online ideal. To understand HyRec's improvement on offline approaches, consider a user whose rating activity fits inside two cycles of offline KNN selection. This user will not benefit from any personalization with an offline approach. This is especially the case for new users, which start with random KNN. In HyRec, on the other hand, users start to form their KNN selection at their first rating and refine it during all their activity. This allows HyRec to achieve personalization quickly, efficiently, and dynamically.

Economic advantage of Hyrec

We now compare the cost of running the HyRec front-end with that of running several offline solutions based on the centralized recommender architecture depicted in Figure 1. In such solutions, a front-end server computes the recommended items in real time upon a client request, while a back-end server periodically runs the KNN selection. Since HyRec leverages user machines to run the KNN-selection task, it significantly reduces the cost of running a recommender system.

To ensure a fair comparison, we first identify a baseline by selecting the least expensive offline solution among several alternatives running on a cluster. Offline-ideal is the offline approach we considered in Sections 5.2 and 5.3. It computes similarities between all pairs of users thereby yielding the ideal KNN at each iteration. Offline-CRec is an offline solution that uses the same algorithm as HyRec (i.e. a sampling approach for KNN) but with a map-reducebased architecture. Both exploit an implementation of the mapreduce paradigm on a single 4-core node [START_REF] Ranger | Evaluating mapreduce for multi-core and multiprocessor systems[END_REF]. Finally, MahoutSingle and ClusMahout are variants based on the user-based CF implementation in Mahout [START_REF]Mahout[END_REF]. Widely employed to add recommendation features to application and websites, Mahout consists of a state-of-the-art open-source machine-learning library by Apache. Both MahoutSingle and ClusMahout exploit the Apache Hadoop platform [5] to parallelize KNN selection on multiple processing cores. MahoutSingle runs on a single 4-core node, while ClusMahout runs on two 4-core nodes. Because all four solutions share the same front-end, we only compare the running times of their KNNselection tasks on the back-end. In all cases, we consider two periods for offline KNN selection: 48 hours on MovieLens and 12 hours on Digg.

Figure 7 depicts the results in terms of wall-clock time. Not surprisingly, we observe a strong correlation between the size of the dataset (in terms of number of users and size of the profile) and the time required to achieve KNN selection. We observe that Offline-CRec consistently outperforms other approaches on all datasets with the exception of ClusMahout using two nodes on the ML1 dataset. On average, Offline-CRec reduces the KNN-selection time by 95.5% and 66.4% with respect to Offline-ideal and ClusMahout, respectively. Moreover, the gap between the wall time required by Offline-CRec and by the other alternatives increases with the size of the dataset. We therefore select Offline-CRec as a baseline to evaluate the gains provided by HyRec in terms of cost.

Specifically we gauge the cost associated with running Offline-CRec and the HyRec front-end on a cloud infrastructure using Ama- zon EC2 services [START_REF]Aws ec2 instances and pricing[END_REF]. For the front-end server of both solutions, we consider the cheapest medium-utilization reserved instances which cost around $681 per year (the Profile table as well as the KNN table need to be stored in memory in order to answer client requests as fast as possible). For the back-end server of Offline-CRec, we consider one of the midrange compute-optimized on-demand instances with a price of $0.6 per hour (on-demand instances allow the content provider to be flexible in operating the offline KNN selection task). The efficiency of Offline-CRec's KNN selection depends on the frequency at which it is triggered: a higher clustering frequency improves recommendation (as shown in Section 5.3) but it makes more frequent use of the on-demand instances, thereby increasing cost.

Based on these estimates, Table 3 considers back-end servers with varying KNN selection periods and summarizes the cost reduction achieved by HyRec over each of them. The numbers show the percentage of the total cost saved by the content provider. We do not consider extra costs for data transfer as the bandwidth overhead generated by HyRec is small and does not exceed the free quota even with the ML3 dataset.

The cost reduction provided by HyRec ranges from 8.6% for ML1 with a KNN selection period of 48 hours to 49.2% for ML3. To compute this last value of 49.2%, we considered a computeoptimized reserved instance over one year. This is cheaper than the number of required on-demand instances, and makes the cost of the offline back-end independent of the KNN selection period. Finally, we observe that the small cost reduction on Digg results from the small user profiles that characterize this dataset.

HyRec server evaluation

We now evaluate the performance of the HyRec server and its ability to scale when increasing the number of clients or the size of user profiles. In doing this, we consider Offline-CRec as a centralized alternative. However, in this section, we only consider its front-end server (referred to as CRec) and assume that its KNN table is up to date as a result of a previous offline computation.

The performance of HyRec mostly depends on the size of profiles and on that of the candidate set. Both these parameters are independent of the size of the dataset; thus we present our experiments on a single dataset, namely ML1, and we artificially control the size of profiles. The other datasets yield similar results. In addition, our experiments model the worst case by considering the largest possi- ble candidate set for a given k (ignoring the decreasing size of the candidate set as the neighborhood converges). Finally, since KNN update messages from the client to the server are negligible when compared to the other messages, we ignore them in the evaluation.

Impact of the profile size.

The size of the user profile directly impacts the performance of the servers (HyRec and CRec). This is clearly application-dependent: for instance users tend to rate news articles more often than they rate movies. Typically, in HyRec, the larger the profile, the larger the size of the messages sent by the HyRec server to a HyRec client. In CRec, the profile size impacts the time spent to compute item recommendation: the larger the profile, the longer the item-recommendation process.

In order to evaluate the impact of the profile size, we run an experiment varying this parameter and evaluate the response time on the HyRec server and on the CRec front-end server. We use ab [START_REF]Apache[END_REF], a benchmark tool provided by Apache. Figure 8 plots the average (over 1000 requests) response time to serve a client request in HyRec and CRec with an increasing profile size. The response time for HyRec includes the time required to compress and decompress JSON messages. In spite of this, HyRec consistently achieves a better response time (by 33% on average) than CRec and this is clearer as the size of profiles increases. This can be explained by the fact that item recommendation on the CRec server takes consistently longer than HyRec's personalization orchestrator takes to build messages.

Impact of the number of users.

The data in Figure 8 refers to a single request by a single user. However, the number of concurrent users definitely impacts the performance of HyRec. Figure 9 compares HyRec with CRec when facing a growing number of concurrent requests from users with profile sizes (ps) of 10 and 100. As expected, with smaller profile sizes, both HyRec and CRec serve requests more rapidly. Yet, HyRec consistently outperforms CRec regardless of the profile size. Results show that HyRec is able to serve as many concurrent requests with a profile size of 1000 as CRec with a profile size of 10. This represents a 100-fold improvement in the scalability of the front-end server for very large profiles. Impact on bandwidth consumption.

Finally, the size of profiles impacts HyRec's bandwidth consumption. Indeed, by delegating expensive computation tasks to clients, HyRec imposes some communication overhead with respect to a centralized architecture. Figure 10 shows the impact of profile size on the size of the JSON messages generated by the HyRec server upon a client request. Results show that the size of JSON messages grows almost linearly with the size of profiles. However, HyRec's front-end server compresses messages on the fly through gzip. This results in a bandwidth consumption of less than 10KB even with a profile size of 500 (compression of around 71%). Note that bandwidth consumption also depends on the size of the candidate set. The size we consider here is an upper bound: the candidate set of a user quickly converges to smaller values. Overall, this shows that HyRec's overhead is negligible when compared to the average size of a current web page (1.3MBytes [6]) and to the content of recommendations themselves, which can include pictures and text.

HyRec client evaluation

We now evaluate the cost of operating HyRec on the client. Our solution introduces a set of tasks on the client side, namely KNN computation, item recommendation, and sending update messages. No data structure needs to be maintained locally. This makes it possible for a user to use HyRec with the same profile from various devices. For HyRec to be sustainable, the operation of HyRec should not significantly impact the performance of a user's machine. Conversely, HyRec should be able to run on any device regardless of its load. We now show that HyRec complies with these requirements.

Impact of HyRec on a client machine.

We first measure the impact of operating the HyRec widget on an application running on a user's device (Figure 11). We consider a laptop on which we run a stress tool [START_REF]Stress: a simple workload generator for linux[END_REF] to create a baseline level of CPU load (x axis in Figure 11). In parallel, we run a simple monitoring tool that executes an infinite loop consisting of a similarity computation. We measure the progress of this tool as the number of iterations it achieves over a given time window. This yields the Baseline curve in Figure 11.

For each of the other curves, we run an additional application in parallel with the stress and the monitoring tools. For HyRec operation, we run an infinite loop that continuously executes the operations of the HyRec widget: KNN selection and item recommendation with a profile size of 100. For Display operation, we run an infinite loop that requests some HTTP content (1, 004 bytes from an RSS feed) from a server and displays it on a web page in a browser. Finally, for Decentralized, we run a fully decentralized recommender comprising P2P network management [START_REF] Jelasity | Gossip-based peer sampling[END_REF] as well as HyRec-like operations (KNN selection and recommendation).

Results demonstrate that the impact of HyRec on the client machine is minimal. HyRec affects the client machine in a similar way as requesting an item from an RSS feed and displaying it on a web page. The plot, also shows that the decentralized recommender has an even lower impact on the client. However, the impact of the decentralized recommender is stable over time since it is mostly due to overlay-network management. Conversely, the impact of HyRec is noticeable only while computing a recommendation. In addition, the operation of the HyRec widget is completely transparent to users, while a P2P recommender requires dedicated software and may encounter limitations related to churn and NAT traversal.

We also measured the impact of the HyRec widget, running in a browser, on other applications running on another tab of the browser while varying CPU usage. Results (not displayed here for space reason) show no impact of the HyRec computation job on other pages within the same browser. This is due to the fact that the browser considers each tab as a different process without links or shared resources. Overall, these experiments demonstrate the negligible impact of the HyRec widget on a user's browser.

Impact of CPU usage on the HyRec client.

We now evaluate to what extent the recommendation tasks of HyRec are impacted by the CPU load on the client machine on two different devices: a smartphone with Android using Wi-Fi and a laptop with Firefox using Ethernet. We measure the time spent by the widget within a browser with a profile size set to 100. To artificially impose load on client machines, we use the antutu smartphone benchmark [START_REF]Antutu[END_REF] and stress [START_REF]Stress: a simple workload generator for linux[END_REF] on the smartphone and the laptop, respectively. Figure 12 shows the average time required on client machines to execute the HyRec recommendation tasks depending on the baseline CPU usage on each of these two devices. We observe that even on a client machine with a CPU loaded at 50%, HyRec tasks run in less than 60ms on the smartphone and less than 10ms on the laptop. We also observe that this time increases only slowly on the laptop as the CPU gets more loaded. This conveys the fact that the HyRec widget can effectively operate even on highly loaded devices. Impact of profile size.

Unlike on the server, the impact of the size of user profiles on the HyRec widget is minimal. Figure 13 shows the duration of HyRec tasks (KNN selection and recommendation) on both a laptop and a smartphone with k =2 0and k =1 0 . Results show that the combined time for KNN selection and recommendation only increases by less than a factor of 1.5 and 7.2 for a laptop and a smartphone, respectively, with profile sizes ranging from 10 to 500 (Figure 13). We observe that although HyRec operations run faster on a laptop than on a smartphone, the impact of profile size remains limited, demonstrating that HyRec scales very well with large profiles.

Impact on bandwidth consumption.

In Section 5.5, we showed that the bandwidth consumption of HyRec is negligible even with large profiles. Here, we observe that, with respect to user machines, it is even lower than that of decentralized recommenders. While the operations carried out by HyRec are similar to those of a P2P recommender, the latter also needs to maintain an overlay network. This leads to continuous profile exchanges (typically every minute) that result in much higher traffic than HyRec, which only causes communication when responding to user requests. For example, on the Digg dataset (with an average of 13 ratings per user), each node in a P2P recommender exchanges approximately 24MB in the whole experiment, while a HyRec widget only exchanges 8kB in the same setting (3% of the of the bandwidth consumption of the P2P solution).

CONCLUDING REMARKS

We report in this paper on the design and evaluation of HyRec, the first user-based collaborative-filtering system with a hybrid architecture. The challenge for a hybrid system consists in deciding what to compute at the clients and what to maintain at the server in order to provide the scalability of P2P approaches while retaining a centralized orchestration. HyRec decomposes the KNN computation between server and clients in an original manner. Clients perform local KNN iterations, while the server stores intermediate results and makes them immediately available to all other clients. This not only provides scalability improvements with respect to centralized (possibly cloud-based) solutions, but it also overcomes the connectivity limitations of completely decentralized ones. We show that HyRec is cost-effective as it significantly reduces the cost of recommendation. The motivation underlying HyRec is to democratize personalization by making it accessible to any content provider without requiring huge investments. HyRec is generic and can operate in many contexts. In its current version, it adopts a user-based CF scheme. However, it can use any data filtering algorithm that can be split among users' web browsers. Experimenting with several such algorithms in HyRec constitutes an interesting future perspective.

Applying HyRec in other contexts may also require additional optimizations. For instance, as shown in Section 5, the size of profiles can have an impact on the overall system performance. In our implementation, we compressed profiles through gzip (which provides an important compression ratio for a tag-based format such as JSON). But this might not always suffice. The size of user profiles depends on the very nature of the application as well as on the number of users in the system. The content provider may thus also constrain profiles by selecting only specific subsets of items, for example those rated within a specific time window.

Another important aspect is the Quality-of-Service perceived by the end user. A good Internet connection and a powerful device will provide recommendations much faster than a poor connection or an old device. However, even in sub-optimal conditions, the delay to display recommendations does not block the display of the rest of the web page thanks to the asynchronous nature of HyRec's widget. Moreover, recent technologies like support for JavaScript threads in HTML5 [START_REF] Bipin | Multithreading in web pages using web workers[END_REF] may further improve the performance of HyRec and encourage further exploration of hybrid web architectures.

Finally, the possibility of attacks and their potential impact can also be an important factor in determining whether to adopt a hybrid architecture. HyRec limits the impact of untrusted and malicious nodes: each user computes only its own recommendations. Furthermore, as we pointed out in Section 3.1, HyRec does not leak the browsing history or the exact profile-identity mapping of other users. De-anonymizing HyRec's anonymous mapping is difficult if the data in profiles cannot be inferred from external sources such as social networks [START_REF] Narayanan | De-anonymizing social networks[END_REF] or other datasets [START_REF] Narayanan | How to break anonymity of the netflix prize dataset[END_REF]. For privacysensitive applications such as recommending a doctor to a patient, it will however be interesting to enrich HyRec with stronger privacy mechanisms, such as homomorphic encryption [START_REF] Canny | Collaborative filtering with privacy via factor analysis[END_REF], or to explore how to provide guarantees like differential privacy [START_REF] Dwork | Differential privacy: a survey of results[END_REF].

Figure 1 :

 1 Figure 1: Centralized, decentralized, and hybrid (HyRec) architectures for a recommender system.

Figure 2 :

 2 Figure 2: Timeline: a centralized approach vs. HyRec.

Figure 3 :

 3 Figure 3: Average view similarity on ML1 dataset for HyRec and ideal KNN.

Figure 4 :

 4 Figure 4: Impact of the user's activity on the quality of the KNN selection of HyRec (ML1 dataset, k =10).

Figure 5 :Figure 6 :

 56 Figure 5: Convergence of the candidate set size (ML1 dataset).

Figure 7 :

 7 Figure 7: Time to compute the k nearest neighbors on ML and Digg workloads.

Figure 8 :

 8 Figure 8: Average response time for HyRec versus CRec according to the profile size.

Figure 9 :

 9 Figure 9: HyRec vs CRec with a growing number of concurrent requests.

Figure 10 :

 10 Figure 10: HyRec: Profile size versus bandwidth overhead.

Figure 11 :

 11 Figure 11: Impact of HyRec widget, a decentralized recommender and a display operation on a client machine.

Figure 12 :

 12 Figure 12: Impact of the client machine load on the HyRec client.

Figure 13 :

 13 Figure 13: Profile size's impact on the HyRec widget.

  Algorithm 2 Recommendation: α(Su,Pu) where Pu is the profile of the user u and Su is a candidate set for user u

	1: var popularity[];
	2: for all uid : user in Su do
	3: for all iid : item in Su[uid].getP rof ile() do
	4:	if Pu does not contain iid then
	5:	popularity[iid]++;
	6:	end if
	7: end for
	8: end for
	9: Ru = subList(r, sort(popularity));
	10: return: Ru, the r most popular items;

Table 2 :

 2 Dataset statistics.

		Users	Items	Ratings	Avg ratings
	ML1	943	1,700	100,000	106
	ML2	6,040	4,000	1,000,000	166
	ML3	69,878 10,000 10,000,000	143
	Digg	59,167 7,724	782,807	13

Table 3 :

 3 Cost reduction provided by HyRec with respect to a centralized back-end server with varying KNN selection periods.

	Dataset	48h	24h	12h
	ML1	8.6%	15.8% 27.4 %
	ML2	31%	47.6 % 49.2 %
	ML3	49.2 % 49.2 % 49.2 %
		12h	6h	2h
	Digg	2.5%	5.0%	9.5%

We omit the real name for confidentiality reasons.

Acknowledgments. This work was partially funded by the Web Alter-Ego Google Focused Award, the French ANR project Socio-Plug (ANR-13-INFR-0003), and the Labex CominLabs excellence laboratory (ANR-10-LABX-07-01) through the DeSceNt project.


Davide Frey
email: davide.frey@inria.fr

Anne-Marie Kermarrec

Christopher Maddock

Andreas Mauthe
email: a.mauthe@lancaster.ac.uk

François Taïani
email: francois.taiani@irisa.fr

Adaptation for the Masses: Towards Decentralized Adaptation in Large-Scale P2P Recommenders

Keywords: I.5.3 [Clustering]: Algorithms, D.4.7 [Organization and Design]: Distributed systems, K.6.4 [System Management]: Centralization/decentralization Collaborative filtering, Recommendation systems, Heterogeneity, Adaptivity

Decentralized recommenders have been proposed to deliver privacy-preserving, personalized and highly scalable on-line recommendation services. Current implementations tend, however, to rely on hard-wired, mechanisms that cannot adapt. Deciding beforehand which hard-wired mechanism to use can be difficult, as the optimal choice might depend on conditions that are unknown at design time. In this paper, propose a framework to develop dynamically adaptive decentralized recommendation systems. Our proposal supports a decentralized form of adaptation, in which individual nodes can independently select, and update their own recommendation algorithm, while still collectively contributing to the overall system's services.

INTRODUCTION

The Web 2.0 has reshaped the modern-day Internet. Billions of users across the globe access content produced not only by well-known websites, but also by users themselves through collaborative platforms such as online forum or social-networking websites [START_REF]Facebook: Company info -statistics[END_REF]. This results in a spectacular growth in available content, and raises many engineering challenges on how to build architectures that can manage this content in a scalable, resilient, and efficient manner.

Recommendation has emerged as a key service to navigate the resulting data deluge. Recommender systems exploit a user's personal data and past on-line behavior to propose personalized services, resources, and information. Designing scalable and privacy-preserving recommenders is hard, and one promising approach consists in exploiting highly scalable and fully decentralized mechanisms such as gossip protocols [START_REF] Leroy | Cold start link prediction[END_REF][START_REF] Bertier | The gossple anonymous social network[END_REF], or distributed hash tables [START_REF] Tirado | Affinity p2p: A self-organizing content-based locality-aware collaborative peer-to-peer network[END_REF].

These decentralized recommenders have however been limited so far to relatively homogeneous configurations. They typically rely on one similarity metric [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF] to selforganize large numbers of users in implicit communities and offer powerful means to search, mine, and compute personalized recommendations. Figuring out the right similarity metric that best fits the needs of a large collection of users is however, highly challenging.

To address this challenge, we explore in this paper how dynamic adaptation can be applied to large-scale decentralized recommenders by allowing each individual nodes to opt autonomously between different topological options. This work seeks to extend early explorations in the field of largescale peer-to-peer self-adaptation [START_REF] Kermarrec | Diverging towards the common good: heterogeneous self-organisation in decentralised recommenders[END_REF], and our early results demonstrate the feasibility of decentralized self-adaptation in peer-to-peer recommender systems.

The paper is organized as follows. Section 2 provides some background and motivates our work. Section 3 presents our proposal. We present our evaluation approach in Section 4. Evaluation results are presented in Section 5, related work in Section 6, and the conclusion in Section 7.

BACKGROUND

Recommendation systems have transformed the way we access content on the Internet. Initially introduced to prioritize Usenet news [START_REF] Konstan | Grouplens: Applying collaborative filtering to usenet news[END_REF], they are becoming an integral part of most online applications: from social networks [START_REF]Facebook: Company info -statistics[END_REF] to online media [START_REF] Song | A survey of music recommendation systems and future perspectives[END_REF], from e-commerce [START_REF] Linden | com recommendations: Item-to-item collaborative filtering[END_REF] to news websites [START_REF] Das | Google news personalization: scalable online collaborative filtering[END_REF]. Because of their success, recommendation systems are today hitting the boundaries of traditional system-engineering practices. But, in the vast majority of cases, they remain based around centralized designs.

Limitations of Centralized Recommenders

Centralization comes with two critical drawbacks. First, centralization raises the specter of a big brother society, in Second, the coexistence of multiple competing centralized systems leads to a 'data siloing' effect. Information about the interests of a user is scattered across a multitude of competing services. This not only makes it impossible for a service to reuse data gathered by another player. But it also makes it very difficult for users themselves to exploit their personal data directly without intermediaries [START_REF] Yeung | Decentralization: The future of online social networking[END_REF].

These crucial limitations have motivated research on decentralized recommendation systems [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF][START_REF] Baraglia | A peer-to-peer recommender system for self-emerging user communities based on gossip overlays[END_REF][START_REF] Moreno | Decentralized recommender systems for mobile advertisement[END_REF].

Epidemic Decentralized Recommendation

A particularly successful technology for decentralized recommendation consists of implicit interest-based overlays [START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF]. In these overlays each user is associated with an independent computer that stores the user's information, and represents the user in the system. These computers are usually referred to as nodes to emphasize their distributed nature. The system then organizes these nodes in a peer-topeer topology (or overlay) in which each node is connected to a limited number of other nodes (the node's neighbors). (In the following we use user and node interchangeably.)

These overlays seek to connect users with their most similar other users in the system, according to a similarity metric such as profile overlap, Jaccard, or Cosine similarity. The system then uses the resulting k nearest neighbors or knn (where k is small) to deliver personalized recommendation in a scalable on-line manner. Figure 1 illustrates this operation. In this example each user is connected through the system to three other users, based on his/her on-line browsing history. Alice has been found to be most similar to Frank, Ellie, and Bob; and Bob has been found to be most similar to Carl, Dave, and Alice.

Although Bob and Alice have been detected to be very similar, their browsing histories are not identical: Bob has not visited Le Monde, but has read the New York Times, which Alice has not. The system can use Bob's browsing history to recommend the New York Times to Alice, and reciprocally use Alice's history to recommend Le Monde to Bob, thus providing a form of decentralized collaborative filtering [START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF].

Gossip algorithms [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF] turn out to be particularly useful in building such interest-based overlays. By means of periodic pair-wise information exchanges, they can effectively create clusters of similar users within the system. Users typically start with a random neighborhood, provided by a random peer sampling service [START_REF] Jelasity | Gossip-based peer sampling[END_REF]. The protocol then runs in asynchronous rounds, during which each user repeatedly exchanges information with its neighbors, and seeks to improve its neighborhood in terms of similarity.

For instance, in Figure 2, Alice is interested in hearts, and is currently connected to Frank, who also likes hearts, and also Ellie, who is only interested in diamonds. When Alice exchanges her neighbor list with Bob, she learns of Bob's neighbors, and finds out about Carl, who shares her interest in hearts. As such, Alice drops Ellie from her neighborhood, and replaces her with Carl, who will be more useful in providing recommendations to Alice.

This greedy sampling procedure is usually complemented by also considering a few random peers (returned by a decentralized peer sampling service [START_REF] Jelasity | Gossip-based peer sampling[END_REF]) as potential neighbors to escape local minima.

Self-Adaptive Implicit Overlays

The overall performance of a service using a knn overlay critically depends on the quality of the similarity metric it uses. Unfortunately, deciding at design time which similarity metric will work best for all nodes is highly challenging. The same metric might not work equally well for all users [START_REF] Kermarrec | Diverging towards the common good: heterogeneous self-organisation in decentralised recommenders[END_REF], and imposing a homogeneous choice to all nodes may be sub-optimal. Further, user behavior might evolve over time, thereby rendering a static metric choice sub-efficient, even though this choice worked well initially.

Despite these limitations, existing decentralized recommendation systems almost invariably use a single similarity metric that is statically selected at design time [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Bai | Gossiping personalized queries[END_REF][START_REF] Baraglia | A peer-to-peer recommender system for self-emerging user communities based on gossip overlays[END_REF].

The research introduced in this paper investigates the question of whether it is possible to instead both find, and update a node's optimal metric dynamically, during the recommendation process. Adapting a node's similarity metric is, however, particularly difficult for at least three reasons. Firstly, in the similarity-based overlays we consider, the nodes only have access to a limited subset of the whole system (i.e. their neighborhood ) and must make adaptation decisions based on this limited context. This partial knowledge means that it may not be possible to implement a workable adaptation mechanism in such systems, since too much information is missing.

Second, there is a circular dependency between the information available to nodes for adaptation decisions and the actual decision taken. A node must rely on its neighborhood to decide whether a new metric might be preferable to the metric it currently uses. Though this neighborhood depends in turn on the actual metric being used by the node, adding further instability to the adaptation.

Finally, because of the decentralized nature of these systems, nodes should ideally be able to adapt independently from each other, in order to limit synchronization and max- sim(items, items(q)) 10: end function imize scalability. The overall convergence of the overlay is, however, an emergent behavior that depends on the collaboration of all nodes. Thus, the central question is: can nodes adapt independently while preserving the system's overall convergence?

DECENTRALIZED ADAPTATION

System Model and Overlay Construction

We assume a peer-to-peer system in which each node p possesses a set of items, items(p) (in our evaluation: Twitter subscriptions), and maintains a set of k neighbors, where k, the fan-out, is a fixed parameter of the system (k = 10 in our experiments). p's neighbors are noted Γ(p), and by extension, Γ 2 (p) are p's neighbors' neighbors. Each node p is associated with a similarity metric, noted p.sim, which takes two sets of items and returns a similarity value.

The main loop of our algorithm (dubbed Similitude) is shown in Algorithm 1 (when executed by node p). Ignoring line 3 for the moment, lines 2 and 4 implement the greedy knn mechanism presented in Section 2.2. At line 4, argtop k selects the k nodes of cand (the candidate nodes that may become p's new neighbors) that maximize the similarity expression p.sim items(p), items(q) .

Recommendations are generated at lines 5 and 6 from the set itΓ of subscriptions of all users in p's neighborhood (noted items Γ(p) ). Recommendations are ranked using the function score at line 8, with the similarity score of the user(s) they are sourced from. Recommendations suggested by multiple users take the sum of all relevant scores. The top m recommendations from itΓ (line 6) are suggested to the user (or all of them if there are less than m).

Dynamic Adaptation of Similarity

The adaptation mechanism we propose, adaptsim, is called at the start of each clustering round (line 3 of Algorithm 1) and is shown in Algorithm 2. A node p estimates the potential of each available metric (s ∈ S at line 2) using the function eval sim(s). In eval sim(s), p hides a fraction f of its own (lines 8 and 9) and creates a 'temporary potential Γ f for each similarity metric available (line 10). (We use f = 20% in our evaluation.) From each temporary neighborhood, the node generates a set of recommendations (lines 11 and 12, see Section 3.1) and evaluates them against the fraction f of internally hidden items. This allows it to associate each similarity s with a score S

8: hidden f ← proportion f of items(p) 9: visible f ← items(p) \ hidden f 10: Γ f ← argtop k q∈cand s visible f , items(q) 11: it f ← items Γ f \ visible f 12: rec f ← argtop m i∈it f score(i, s, visible f , Γ f ) 13: return S = |hidden f ∩ rec f | |hidden f | 14: end function
consisting of the fraction of hidden f interests matched -'recall' (line 13). Node p repeats this evaluation process four times and averages the results (operator avg 4 at line 2 of Algorithm 2). Using these averaged scores, p computes the set of the highest-achieving metrics (top sims). (This is a set as multiple metrics may achieve the same score.) If the current metric-in-use p.sim is in top sims, p continues to use it; if not, p selects a random metric from top sims (lines 3-4).

After selecting a new metric, a node suspends the metricselection process for two rounds during which it only refines its neighbors. This cool-off period allows the newly selected metric to start building a stable neighborhood thereby limiting oscillation and instability.

EVALUATION APPROACH

We validate the adaptation strategies we propose by carrying out simulations on a data set obtained from Twitter. In this section we present our evaluation protocol, before discussing our experimental results in Section 5.

Data Set

Our evaluation is based on the profiles of 1,000 similarlygeolocated Twitter users, randomly selected from the larger data set presented in [START_REF] Carretero | Geology: Modular georecommendation in gossip-based social networks[END_REF] 1 . The profile of each user is composed of their twitter subscriptions (feeds). All feeds known to less than 20 users were removed, as these feeds are of little interest to the collaborative filtering process. Finally, all users with less than five remaining subscriptions were also removed. Once this process was complete, 833 users remained, with a mean of 66 subscriptions per user.

Evaluation Metrics

To evaluate the success of the experiment, we record four metrics: Recall, Precision, Number of 'Optimal Metrics', and Level of Instability.

A recommendation system offers two main points of evaluative interest: the number of valid recommendations which can be made, and the accuracy of the recommendation set as a whole. These two aspects are measured using recall (measuring the ability of the system to return many correct recommendations) and precision (measuring the ability of the system to return few incorrect recommendations).

Alongside these two general metrics for recommendation systems, we also use two more specific metrics. We first count how many nodes reach their optimal similarity metrics. We define more precisely what we understand by optimal in Section 4.5. Finally, we observe the level of instability within the system, by recording the number of nodes switching metric during each round.

Simulator and Cross Validation

We use cross-validation to measure the quality of the recommendations returned by our system. We simulate our system using 80% of user's profiles (visible data set) to construct the similarity-based overlay and compute recommendations, and use the remaining 20% (hidden data set) to calculate the quality of these recommendations.

Our simulations use the following parameters: Each node is randomly assigned a neighborhood of 10 nodes, as well as a randomly selected similarity metric to start the refinement process. Simulations run for 200 rounds. 66 suggestions are returned to each node in each round, and the recall and precision metrics are computed based on these suggestions. We use two rounds of cool-off by default.

We repeat each simulation 10 times and average the results. After completing each set of 200 rounds, all nodes clear their data structures and the simulation restarts.

Similarity Metrics

Our evaluation uses four similarity metrics: Overlap, Big, OverBig and Jaccard [START_REF] Kermarrec | Diverging towards the common good: heterogeneous self-organisation in decentralised recommenders[END_REF], shown in Fig. 3. These metrics are sufficiently different to represent distinct similarity choices for each node, and offer a representative adaptation scenario.

Overlap is a simple count of the subscriptions shared by a user and its neighbor. As such, it would have the tendency to favor users with a large number of subscriptions. Big simply counts the number of subscriptions of the neighbor, presuming that the greater the number of subscriptions available, the more likely a match is to be found somewhere in the list. This likewise favors users with a larger number of subscriptions. Overbig works by combining Big and Overlap -which allows the least similar high-subscription users to be discredited. Finally Jaccard makes the overlap of subscriptions relative to the total number of subscriptions of the two users, and thus, provides improved results for users with fewer subscriptions.

It is important to note that the actual set of metrics is not our main focus. Rather, we are interested in the adaptation process, and seek to demonstrate how recommendations can be improved by adjusting nodes' similarity metrics.

Static Metrics Allocations

We compare our approach to five static (i.e. non-adaptive) system configurations, which serve as baselines for our eval-

Overlap(ui, uj) = |subsi ∩ subsj| Big(ui, uj) = |subsj| OverBig(ui, uj) = Overlap(ui, uj) + Big(ui, uj) Jaccard(ui, uj) = Overlap(u i ,u j )
subs i ∪subs j uation. In the first four baseline configurations, we statically allocate the same metrics to all nodes from the set of possible metrics defined in Fig. 3 (Overlap, Big, OverBig, and Jaccard ). These baselines are static and homogeneous.

The fifth (HeterRand) randomly allocates one of the four above metrics to each node. This configuration corresponds to a situation in which the system has no a-priori knowledge regarding optimal metrics, and does not use dynamic adaptation.

EXPERIMENTAL RESULTS

Static Baseline

The distribution of optimal metrics obtained by individual nodes (Sec. 4.5) is shown in Fig. 4. To estimate variability, the entire experiment is repeated twice, and the two sets of results compared node by node. In total, 88.2% of nodes report the same list of optimal metrics across both tests. Of the 98 nodes that did not, 20% listed optimal metrics which were a subset of those they had found in the first run, and all but one of this 20% had under 30 subscriptions. (Well below the mean of 66.) 42 nodes were unable to settle on a single optimal metric, all but one of those recording no difference between any of the four metrics. These nodes were generally those with the smallest amount of data available.

The distribution in Fig. 4 diverges from that of [START_REF] Kermarrec | Diverging towards the common good: heterogeneous self-organisation in decentralised recommenders[END_REF] as we did not use the exact same dataset. This highlights the difficult of selecting a static metric at a system's design time.

Similitude

We test Similitude with a cool-off period of two rounds. We first evaluate the convergence of recall and precision for Similitude and compare it with that of HeterRand (Figures 5 and 6). We then analyze the number of users that select one of the optimal metrics as discussed in Sec. 5.1 (Fig. 7), and the switching activity of users (Fig. 8). Table 1 completes these results with the recall and precision obtained at round 200 (converged state), while Table 2 presents converged-state results for non-adaptive solutions exploiting each predefined static metric.

Results show that Similitude allows nodes to both find their optimal metric and switch to it. Compared to a static random allocation of metrics (HeterRand), Similitude improves recall by 17.8% (from 0.28 to 0.34), and precision by 22% (from 0.038 to 0.046) as shown in Table 1.

Table 2 shows that the average performance of nonadaptive metrics is very close to that of HeterRand. Similitude outperforms all but one of these static homogeneous metrics (Jaccard, which shows a recall of 0.39 compared to 0.34). However, selecting Jaccard statically would require knowing that this metric performs best, a knowledge that is often not available in evolving systems. As users' behaviors evolve, the high gain of Jaccard might be replaced by that of another metric. Similitude makes it instead possible to achieve stable performance in spite of dynamic behavior.

Discussion

Despite these encouraging results, Similitude opens several directions for improvement. First, Fig. 7 shows that only 46.1% of nodes (384 out of 833) eventually switch to an optimal metric. This leads to the question of why so many nodes are settling for a sub-par metric. A second improvement direction results from Fig. 8: while most nodes choose their favorite metric within 20 cycles, approximately 20% of them never settle for any metric. To address this instability, we are investigating solutions that average the scores obtained by a metric over multiple rounds.

Finally, we observe that a node chooses its metric based on its current neighborhood. This tends to favor the metric that created this neighborhood, even if another one might yield better results on a different neighborhood. We are thus evaluating a model in which nodes evaluate metrics against randomly selected neighborhoods.

RELATED WORK

Several research efforts have recently concentrated on decentralized recommenders [START_REF] Han | A scalable p2p recommender system based on distributed collaborative filtering[END_REF][START_REF] Miller | Pocketlens: toward a personal recommender system[END_REF]1,[START_REF] Boutet | Privacy-Preserving Distributed Collaborative Filtering[END_REF][START_REF] Schiavoni | Whisper: Middleware for confidential communication in large-scale networks[END_REF] to investigate their advantages in terms of scalability and privacy. Earlier approaches exploit distributed hash tables (DHTs) in the context of recommendation. For example, PipeCF [START_REF] Han | A scalable p2p recommender system based on distributed collaborative filtering[END_REF] and PocketLens [START_REF] Miller | Pocketlens: toward a personal recommender system[END_REF] propose a Chord-based CF systems to decentralize the recommendation process on a P2P infrastructure. Yet, more recent solutions have concentrated on the use of randomized and gossip-based protocols [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Kermarrec | Application of random walks to decentralized recommender systems[END_REF][START_REF] Baraglia | A peer-to-peer recommender system for self-emerging user communities based on gossip overlays[END_REF].

Recognized as a fundamental tool for information dissemination [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Mega | Efficient dissemination in decentralized social networks[END_REF], Gossip protocols exhibit innate scalability and resilience to failures. As information is generally copied over many links, a single lost connection generally has no effect on information dissemination. Yet, their probabilistic nature also makes gossip protocols particularly suited to applications involving uncertain data, like recommendation.

Olsson's Yenta [START_REF] Olsson | Decentralised social filtering based on trust[END_REF] was one of the first systems to employ gossip protocols in the context of recommendation. This theoretical work enhances decentralized recommendation by taking trust between users into account. The Gossple system [START_REF] Bertier | The gossple anonymous social network[END_REF] uses a similar theory to enhance navigation through query expansion and was later extended to news recommendation [START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF]. Finally, in [START_REF] Hegedus | Gossip-based learning under drifting concepts in fully distributed networks[END_REF], Hegedűs et al. present a gossipbased learning algorithm that carries out 'random walks' through a network to monitor concept drift and adapt to change in P2P data-mining.

The adaptive element of our work is partially motivated by [START_REF] Kermarrec | Diverging towards the common good: heterogeneous self-organisation in decentralised recommenders[END_REF], where the authors demonstrate that higher-quality recommendation is achievable when multiple different similarity metrics are used in a heterogeneous fashion, across a network. Contrary to the approach we have presented, [START_REF] Kermarrec | Diverging towards the common good: heterogeneous self-organisation in decentralised recommenders[END_REF] exploits a static a-priori selection of metrics, and does not propose any mechanism to select metrics dynamically. Other related work has looked at matching events against interests in pub-sub infrastructures, and considered how the infrastructure could use self-adaptation within an overlay network, to adapt to changes in the application traffic [START_REF] Di Nitto | Reconfiguration primitives for self-adapting overlays in distributed publish-subscribe systems[END_REF].

CONCLUSION

We demonstrated the viability of an adaptive, decentralized recommendation system that exploits a variety of similarity metrics. Our results indicate that such a system can offer an improvement over existing homogeneous methods.

The adaptation algorithm we have presented remains basic: we plan to investigate how the choice of adaptation could be further refined, for instance by taking into account the decisions of neighboring nodes, or by trying to minimize the advantage of the current metrics over its competitors. Also it would be interesting to evaluate a practical implementation of such a network. Our study exhibits limitations resulting from the characteristics of the data set we used (sparsity and small size). Sparsity is also likely to occur in a real implementation. However, running the system with a larger, less refined data set may provide an interesting insight into more potential problems the system may face.

Figure 2 :

 2 Figure 1: Recommendation in an implicit overlay

Figure 3 :

 3 Figure 3: The four similarity metrics used

Figure 4 :

 4 Figure 4: Distribution of optimal metrics

  Figure 5: Recall

Figure 6 Figure 7 :Figure 8 :

 678 Figure 6: Precision

  Algorithm 1 Similitude's Main Loop by node p 1: in every round do 2: cand ← Γ(p) ∪ Γ 2 (p) ∪ 1 random node 3: adaptsim(cand)

	4: Γ(p) ← argtop k	p.sim items(p), items(q)
	q∈cand
	5: itΓ ← items Γ(p) \ items(p)
	6: rec ← argtop m	score i, p.sim, items(p), Γ(p)
	i∈it Γ 7: end round
	8: function score(i, sim, items, Γ)
	9: return
	q∈Γ:
	i∈items(q)

  Algorithm 2 Similarity adaptation by node p 1: function adaptsim(cand) 2: top sims ← argmax s∈S avg 4 eval sim(s, cand) 3: if p.sim ∈ top sims then 4: p.sim ← random element from top sims 5: end if 6: end function 7: function eval sim(s, cand)

Table 2 :

 2 Evaluating static homogeneous metrics. The gain columns show the gains of each row over the baseline(HeterRand)

	similarity recall	gain precision	gain
	HeterRand 0.2850	-	0.0383	-
	Similitude	0.3358 17.82%	0.0467 22.04%
	Table 1: Gain of Similitude over HeterRand
	similarity	recall	gain precision	gain
	Jaccard	0.3867	35.70%	0.0517	35.16%
	Overlap	0.3452	21.11%	0.0449	17.33%
	Big	0.2075 -27.19%	0.0283 -25.91%
	OverBig	0.1984 -30.40%	0.0278 -27.35%
	Average	0.2844 -0.19%	0.0382 -0.19%

An anonymized version of this data set is available at http://ftaiani.ouvaton.org/ressources/ onlyBayLocsAnonymised_21_Oct_2011.tgz

Acknowledgments

This work has been partially funded by the French National Research Agency (ANR) project SocioPlug under contract ANR-13-INFR-0003 (http://socioplug.univ-nantes.fr).