Parallel and Distributed Collaborative Filtering: A Survey
---
paper_title: Evaluating collaborative filtering recommender systems

paper_content:

Recommender systems have been evaluated in many, often incomparable, ways. In this article, we review the key decisions in evaluating collaborative filtering recommender systems: the user tasks being evaluated, the types of analysis and datasets being used, the ways in which prediction quality is measured, the evaluation of prediction attributes other than quality, and the user-based evaluation of the system as a whole. In addition to reviewing the evaluation strategies used by prior researchers, we present empirical results from the analysis of various accuracy metrics on one content domain where all the tested metrics collapsed roughly into three equivalence classes. Metrics within each equivalency class were strongly correlated, while metrics from different equivalency classes were uncorrelated.
---
paper_title: Introduction to parallel computing: design and analysis of algorithms

paper_content:

Introduction. What is Parallel Computing? The Scope of Parallel Computing. Issues in Parallel Computing. Organization and Contents of The Text. Bibliographic Remarks. Problems. References. Models of Parallel Computers. A Taxonomy of Parallel Architectures. An Idealized Parallel Computer. Dynamic Interconnection Networks. Static Interconnection Networks. Embedding Other Networks Into a Hypercube. Routing Mechanisms For Static Networks. Communication Costs in Static Interconnection Networks. Cost-Performance Tradeoffs. Architectural Models For Parallel Algorithm Design. Bibliographic Remarks. References. Basic Communication Operations. Simple Message Transfer Between Two Processors. One-To-All Broadcast. All-To-All Broadcast, Reduction, and Prefix Sums. One-To-All Personalized Communications. All-To-All Personalized Communications. Circular Shift. Faster Methods For Some Communication Operations. Summary. Bibliographic Remarks. Problems. References. Performance and Scalability of Parallel Systems. Performance Metrics For Parallel Systems. The Effect of Granularity and Data Mapping On Performance. The Scalability of Parallel Systems. The Isoefficiency Metric of Scalability. Sources of Parallel Overhead. Minimum Execution Time and Minimum Cost-Optimal Execution Time. Other Scalability Metrics and Bibliographic Remarks. Problems. References. Dense Matrix Algorithms. Mapping Matrices Onto Processors. Matrix Transpositon. Matrix-Vector Multiplication. Matrix Multiplication. Solving a System of Linear Equations. Bibliographic Remarks. Problems. References. Sorting. Issues in Sorting On Parallel Computers. Sorting Networks. Bubble Sort and Its Variants. Quicksort. Other Sorting Algorithms. Bibliographic Remarks. Problems. References. Graph Algorithms. Definitions and Representation. Minimum Spanning Tree: Prim's Algorithm. Single-Source Shortest Paths: Dijkstra's Algorithms. All-Pairs Shortest Paths. Transitive Closure. Connected Components. Algorithms For Sparse Graphs. Bibliographic Remarks. Problems. References. Search Algorithms For Discrete Optimization Problems. Definitions and Examples. Sequential Search Algorithms. Search Overhead Factor. Parallel Depth-First Search. Parallel Best-First Search. Speedup Anomalies in Parallel Search Algorithms. Bibliographic Remarks. Problems. References. Dynamic Programming. Serial Monadic Dp Formulations. Nonserial Monadic Dp Formulations. Serial Polyadic Dp Formulations. Nonserial Polyadic Dp Formulations. Summary and Discussion. Bibliographic Remarks. Problems. References. Fast Fourier Transform. The Serial Algorithm. The Binary-Exchange Algorithm. The Transpose Algorithm. Cost-Effectiveness of Meshes and Hypercubes For Fft. Bibliographic Remarks. Problems. References. Solving Sparse Systems of Linear Equations. Basic Operations. Iterative Methods. Finite Element Method. Direct Methods For Sparse Linear Systems. Multigrid Methods. Bibliographic Remarks. Problems. References. Systolic Algorithms and Their Mapping Onto Parallel Computers. Examples of Systolic Systems. General Issues in Mapping Systolic Systems Onto Parallel Computers. Mapping One-Dimensional Systolic Arrays. Bibliographic Remarks. Problems. References. Parallel Programming. Parallel Programming Paradigms. Primitive For The Message-Passing Programming Paradigm. Data-Parallel Languages. Primitives For The Shared-Address-Space Programming Paradigm. Fortran D. Bibliographic Remarks. References. Appendix A. Complexity of Functions and Order Analysis. Author Index. Subject Index. 0805331700T04062001
---
paper_title: Distributed Systems: Concepts and Design

paper_content:

Broad and up-to-date coverage of the principles and practice in the fast moving area of Distributed Systems. Distributed Systems provides students of computer science and engineering with the skills they will need to design and maintain software for distributed applications. It will also be invaluable to software engineers and systems designers wishing to understand new and future developments in the field. From mobile phones to the Internet, our lives depend increasingly on distributed systems linking computers and other devices together in a seamless and transparent way. The fifth edition of this best-selling text continues to provide a comprehensive source of material on the principles and practice of distributed computer systems and the exciting new developments based on them, using a wealth of modern case studies to illustrate their design and development. The depth of coverage will enable readers to evaluate existing distributed systems and design new ones.
---
paper_title: Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions

paper_content:

This paper presents an overview of the field of recommender systems and describes the current generation of recommendation methods that are usually classified into the following three main categories: content-based, collaborative, and hybrid recommendation approaches. This paper also describes various limitations of current recommendation methods and discusses possible extensions that can improve recommendation capabilities and make recommender systems applicable to an even broader range of applications. These extensions include, among others, an improvement of understanding of users and items, incorporation of the contextual information into the recommendation process, support for multicriteria ratings, and a provision of more flexible and less intrusive types of recommendations.
---
paper_title: Recommender Systems

paper_content:

The ongoing rapid expansion of the Internet greatly increases the necessity of effective recommender systems for filtering the abundant information. Extensive research for recommender systems is conducted by a broad range of communities including social and computer scientists, physicists, and interdisciplinary researchers. Despite substantial theoretical and practical achievements, unification and comparison of different approaches are lacking, which impedes further advances. In this article, we review recent developments in recommender systems and discuss the major challenges. We compare and evaluate available algorithms and examine their roles in the future developments. In addition to algorithms, physical aspects are described to illustrate macroscopic behavior of recommender systems. Potential impacts and future directions are discussed. We emphasize that recommendation has a great scientific depth and combines diverse research fields which makes it of interests for physicists as well as interdisciplinary researchers.
---
paper_title: Recommender Systems: An Introduction

paper_content:

In this age of information overload, people use a variety of strategies to make choices about what to buy, how to spend their leisure time, and even whom to date. Recommender systems automate some of these strategies with the goal of providing affordable, personal, and high-quality recommendations. This book offers an overview of approaches to developing state-of-the-art recommender systems. The authors present current algorithmic approaches for generating personalized buying proposals, such as collaborative and content-based filtering, as well as more interactive and knowledge-based approaches. They also discuss how to measure the effectiveness of recommender systems and illustrate the methods with practical case studies. The final chapters cover emerging topics such as recommender systems in the social web and consumer buying behavior theory. Suitable for computer science researchers and students interested in getting an overview of the field, this book will also be useful for professionals looking for the right technology to build real-world recommender systems.
---
paper_title: Collaborative Filtering Based Recommendation System: A survey

paper_content:

the most common technique used for recommendations is collaborative filtering. Recommender systems based on collaborative filtering predict user preferences for products or services by learning past user-item relationships from a group of user who share the same preferences and taste. In this paper we have explored various aspects of collaborative filtering recommendation system. We have categorized collaborative filtering recommendation system and shown how the similarity is computed. The desired criteria for selection of data set are also listed. The measures used for evaluating the performance of collaborative filtering recommendation system are discussed along with the challenges faced by the recommendation system. Types of rating that can be collected from the user to rate items are also discussed along with the uses of collaborative filtering recommendation system.
---
paper_title: An empirical comparison of social, collaborative filtering, and hybrid recommenders

paper_content:

In the Social Web, a number of diverse recommendation approaches have been proposed to exploit the user generated contents available in the Web, such as rating, tagging, and social networking information. In general, these approaches naturally require the availability of a wide amount of these user preferences. This may represent an important limitation for real applications, and may be somewhat unnoticed in studies focusing on overall precision, in which a failure to produce recommendations gets blurred when averaging the obtained results or, even worse, is just not accounted for, as users with no recommendations are typically excluded from the performance calculations. In this article, we propose a coverage metric that uncovers and compensates for the incompleteness of performance evaluations based only on precision. We use this metric together with precision metrics in an empirical comparison of several social, collaborative filtering, and hybrid recommenders. The obtained results show that a better balance between precision and coverage can be achieved by combining social-based filtering (high accuracy, low coverage) and collaborative filtering (low accuracy, high coverage) recommendation techniques. We thus explore several hybrid recommendation approaches to balance this trade-off. In particular, we compare, on the one hand, techniques integrating collaborative and social information into a single model, and on the other, linear combinations of recommenders. For the last approach, we also propose a novel strategy to dynamically adjust the weight of each recommender on a user-basis, utilizing graph measures as indicators of the target user's connectedness and relevance in a social network.
---
paper_title: A comparative study of heterogeneous item recommendations in social systems

paper_content:

While recommendation approaches exploiting different input sources have started to proliferate in the literature, an explicit study of the effect of the combination of heterogeneous inputs is still missing. On the other hand, in this context there are sides to recommendation quality requiring further characterisation and methodological research - a gap that is acknowledged in the field. We present a comparative study on the influence that different types of information available in social systems have on item recommendation. Aiming to identify which sources of user interest evidence - tags, social contacts, and user-item interaction data - are more effective to achieve useful recommendations, and in what aspect, we evaluate a number of content-based, collaborative filtering, and social recommenders on three datasets obtained from Delicious, Last.fm, and MovieLens. Aiming to determine whether and how combining such information sources may enhance over individual recommendation approaches, we extend the common accuracy-oriented evaluation practice with various metrics to measure further recommendation quality dimensions, namely coverage, diversity, novelty, overlap, and relative diversity between ranked item recommendations. We report empiric observations showing that exploiting tagging information by content-based recommenders provides high coverage and novelty, and combining social networking and collaborative filtering information by hybrid recommenders results in high accuracy and diversity. This, along with the fact that recommendation lists from the evaluated approaches had low overlap and relative diversity values between them, gives insights that meta-hybrid recommenders combining the above strategies may provide valuable, balanced item suggestions in terms of performance and non-performance metrics.
---
paper_title: Survey on Collaborative Filtering, Content-based Filtering and Hybrid Recommendation System

paper_content:

systems or recommendation systems are a subset of information filtering system that used to anticipate the 'evaluation' or 'preference' that user would feed to an item. In recent years E-commerce applications are widely using Recommender system. Generally the most popular E- commerce sites are probably music, news, books, research articles, and products. Recommender systems are also available for business experts, jokes, restaurants, financial services, life insurance and twitter followers. Recommender systems have formulated in parallel with the web. Initially Recommender systems were based on demographic, content-based filtering and collaborative filtering. Currently, these systems are incorporating social information for enhancing a quality of recommendation process. For betterment of recommendation process in the future, Recommender systems will use personal, implicit and local information from the Internet. This paper provides an overview of recommender systems that include collaborative filtering, content-based filtering and hybrid approach of recommender system.
---
paper_title: Application Domain and Functional Classification of Recommender Systems—A Survey

paper_content:

The amount of scientific and technical information is growing exponentially. As a result, the scientific community has been overwhelmed by the information published in number of new books, journal articles, and conference proceedings. In addition to increasing number of publications, advances in information technology have dramatically reduced the barriers in electronic publishing and distribution of information over networks virtually anywhere in the world. As a result, the scientific community is facing the problem of locating relevant or interesting information. To address the problem of information overload and to sift all available information sources for useful information, recommender systems or filtering systems have emerged. Generally, recommender systems are used online to suggest items that users find interesting, thereby, benefiting both the user and merchant. Recommender systems benefit the user by making him suggestions on items that he is likely to purchase and the business by increase of sales. Filtering information or generation of recommendatio ns by the recommender systems mimic the process of information retrieval systems by incorporating advanced profile building techniques, item/user representation techniques, filtering and recommendation techniques, and profile adaptation techniques. This paper addresses the application domain analysis, functional classification, advantages and disadvantages of various filtering and recommender systems.
---
paper_title: Hybrid Recommender Systems: Survey and Experiments

paper_content:

Recommender systems represent user preferences for the purpose of suggesting items to purchase or examine. They have become fundamental applications in electronic commerce and information access, providing suggestions that effectively prune large information spaces so that users are directed toward those items that best meet their needs and preferences. A variety of techniques have been proposed for performing recommendation, including content-based, collaborative, knowledge-based and other techniques. To improve performance, these methods have sometimes been combined in hybrid recommenders. This paper surveys the landscape of actual and possible hybrid recommenders, and introduces a novel hybrid, EntreeC, a system that combines knowledge-based recommendation and collaborative filtering to recommend restaurants. Further, we show that semantic ratings obtained from the knowledge-based part of the system enhance the effectiveness of collaborative filtering.
---
paper_title: A survey of collaborative filtering based social recommender systems

paper_content:

Recommendation plays an increasingly important role in our daily lives. Recommender systems automatically suggest to a user items that might be of interest to her. Recent studies demonstrate that information from social networks can be exploited to improve accuracy of recommendations. In this paper, we present a survey of collaborative filtering (CF) based social recommender systems. We provide a brief overview over the task of recommender systems and traditional approaches that do not use social network information. We then present how social network information can be adopted by recommender systems as additional input for improved accuracy. We classify CF-based social recommender systems into two categories: matrix factorization based social recommendation approaches and neighborhood based social recommendation approaches. For each category, we survey and compare several representative algorithms.
---
paper_title: A Survey Paper on Recommender Systems

paper_content:

Recommender systems apply data mining techniques and prediction algorithms to predict users' interest on information, products and services among the tremendous amount of available items. The vast growth of information on the Internet as well as number of visitors to websites add some key challenges to recommender systems. These are: producing accurate recommendation, handling many recommendations efficiently and coping with the vast growth of number of participants in the system. Therefore, new recommender system technologies are needed that can quickly produce high quality recommendations even for huge data sets. ::: To address these issues we have explored several collaborative filtering techniques such as the item based approach, which identify relationship between items and indirectly compute recommendations for users based on these relationships. The user based approach was also studied, it identifies relationships between users of similar tastes and computes recommendations based on these relationships. ::: In this paper, we introduce the topic of recommender system. It provides ways to evaluate efficiency, scalability and accuracy of recommender system. The paper also analyzes different algorithms of user based and item based techniques for recommendation generation. Moreover, a simple experiment was conducted using a data mining application -Weka- to apply data mining algorithms to recommender system. We conclude by proposing our approach that might enhance the quality of recommender systems.
---
paper_title: Collaborative Filtering Recommender Systems

paper_content:

Recommender systems are an important part of the information and e-commerce ecosystem. They represent a powerful method for enabling users to filter through large information and product spaces. Nearly two decades of research on collaborative filtering have led to a varied set of algorithms and a rich collection of tools for evaluating their performance. Research in the field is moving in the direction of a richer understanding of how recommender technology may be embedded in specific domains. The differing personalities exhibited by different recommender algorithms show that recommendation is not a one-size-fits-all problem. Specific tasks, information needs, and item domains represent unique problems for recommenders, and design and evaluation of recommenders needs to be done based on the user tasks to be supported. Effective deployments must begin with careful analysis of prospective users and their goals. Based on this analysis, system designers have a host of options for the choice of algorithm and for its embedding in the surrounding user experience. This paper discusses a~wide variety of the choices available and their implications, aiming to provide both practicioners and researchers with an introduction to the important issues underlying recommenders and current best practices for addressing these issues.
---
paper_title: Comparison of collaborative filtering algorithms: Limitations of current techniques and proposals for scalable, high-performance recommender systems

paper_content:

The technique of collaborative filtering is especially successful in generating personalized recommendations. More than a decade of research has resulted in numerous algorithms, although no comparison of the different strategies has been made. In fact, a universally accepted way of evaluating a collaborative filtering algorithm does not exist yet. In this work, we compare different techniques found in the literature, and we study the characteristics of each one, highlighting their principal strengths and weaknesses. Several experiments have been performed, using the most popular metrics and algorithms. Moreover, two new metrics designed to measure the precision on good items have been proposed. The results have revealed the weaknesses of many algorithms in extracting information from user profiles especially under sparsity conditions. We have also confirmed the good results of SVD-based techniques already reported by other authors. As an alternative, we present a new approach based on the interpretation of the tendencies or differences between users and items. Despite its extraordinary simplicity, in our experiments, it obtained noticeably better results than more complex algorithms. In fact, in the cases analyzed, its results are at least equivalent to those of the best approaches studied. Under sparsity conditions, there is more than a 20p improvement in accuracy over the traditional user-based algorithms, while maintaining over 90p coverage. Moreover, it is much more efficient computationally than any other algorithm, making it especially adequate for large amounts of data.
---
paper_title: Context-Aware Recommender Systems for Learning: A Survey and Future Challenges

paper_content:

Recommender systems have been researched extensively by the Technology Enhanced Learning (TEL) community during the last decade. By identifying suitable resources from a potentially overwhelming variety of choices, such systems offer a promising approach to facilitate both learning and teaching tasks. As learning is taking place in extremely diverse and rich environments, the incorporation of contextual information about the user in the recommendation process has attracted major interest. Such contextualization is researched as a paradigm for building intelligent systems that can better predict and anticipate the needs of users, and act more efficiently in response to their behavior. In this paper, we try to assess the degree to which current work in TEL recommender systems has achieved this, as well as outline areas in which further work is needed. First, we present a context framework that identifies relevant context dimensions for TEL applications. Then, we present an analysis of existing TEL recommender systems along these dimensions. Finally, based on our survey results, we outline topics on which further research is needed.
---
paper_title: Comparing State-of-the-Art Collaborative Filtering Systems

paper_content:

Collaborative filteringaims at helping usersfind itemsthey should appreciate from huge catalogues. In that field, we can distinguish user-based, item-basedand model-basedapproaches. For each of them, many options play a crucial role for their performances, and in particular the similarity function defined between users or items, the number of neighbors considered for user- or item-based approaches, the number of clusters for model-based approaches using clustering, and the prediction function used. ::: ::: In this paper, we review the main collaborative filtering methods proposed in the litterature and compare them on the same widely used real dataset called MovieLens, and using the same widely used performance measure called Mean Absolute Error(MAE). This study thus allows us to highlight the advantages and drawbacks of each approach, and to propose some default options that we think should be used when using a given approach or designing a new one.
---
paper_title: Matrix Factorization Model in Collaborative Filtering Algorithms: A Survey

paper_content:

Abstract Recommendation Systems (RSs) are becoming tools of choice to select the online information relevant to a given user. Collaborative Filtering (CF) is the most popular approach to build Recommendation System and has been successfully employed in many applications. Collaborative Filtering algorithms are much explored technique in the field of Data Mining and Information Retrieval. In CF, past user behavior are analyzed in order to establish connections between users and items to recommend an item to a user based on opinions of other users. Those customers, who had similar likings in the past, will have similar likings in the future. In the past decades due to the rapid growth of Internet usage, vast amount of data is generated and it has becomea challenge for CF algorithms. So, CF faces issues with sparsity of rating matrix and growing nature of data. These challenges are well taken care of by Matrix Factorization (MF). In this paper we are going to discuss different Matrix Factorization models such as Singular Value Decomposition (SVD), Principal Component Analysis (PCA) and Probabilistic Matrix Factorization (PMF). This paper attempts to present a comprehensive survey of MF model like SVD to address the challenges of CF algorithms, which can be served as a roadmap for research and practice in this area.
---
paper_title: Decentralised Social Filtering based on Trust

paper_content:

This paper describes a decentralised approach to social filtering based on trust between agents in a multiagent system. The social filtering in the proposed approach is built on the interactions between collaborative software agents performing content-based filtering. This means that it uses a mixture of content-based and social filtering and thereby, it takes advantage of both methods.
---
paper_title: Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design

paper_content:

Despite recent excitement generated by the peer-to-peer (P2P) paradigm and the surprisingly rapid deployment of some P2P applications, there are few quantitative evaluations of P2P systems behavior. The open architecture, achieved scale, and self-organizing structure of the Gnutella network make it an interesting P2P architecture to study. Like most other P2P applications, Gnutella builds, at the application level, a virtual network with its own routing mechanisms. The topology of this virtual network and the routing mechanisms used have a significant influence on application properties such as performance, reliability, and scalability. We have built a "crawler" to extract the topology of Gnutella's application level network. In this paper we analyze the topology graph and evaluate generated network traffic. Our two major findings are that: (1) although Gnutella is not a pure power-law network, its current configuration has the benefits and drawbacks of a power-law structure, and (2) the Gnutella virtual network topology does not match well the underlying Internet topology, hence leading to ineffective use of the physical networking infrastructure. These findings guide us to propose changes to the Gnutella protocol and implementations that may bring significant performance and scalability improvements. We believe that our findings as well as our measurement and analysis techniques have broad applicability to P2P systems and provide unique insights into P2P system design tradeoffs.
---
paper_title: Peer-to-peer based recommendations for mobile commerce

paper_content:

With the increasing number of mobile commerce facilities, there are challenges in providing customers useful recommendations about interesting products and services. In this paper a Peer-to-Peer (P2P) based collaborative filtering architecture for the support of product and service recommendations for mobile customers is considered. Mobile customers are represented by software assistant agents that act like peers in the processing of recommendations.
---
paper_title: Distributed collaborative filtering with domain specialization

paper_content:

User data scarcity has always been indicated among the major problems of collaborative filtering recommender systems. That is, if two users do not share sufficiently large set of items for whom their ratings are known, then the user-to-user similarity computation is not reliable and a rating prediction for one user can not be based on the ratings of the other. This paper shows that this problem can be solved, and that the accuracy of collaborative recommendations can be improved by: a) partitioning the collaborative user data into specialized and distributed repositories, and b) aggregating information coming from these repositories. This paper explores a content-dependent partitioning of collaborative movie ratings, where the ratings are partitioned according to the genre of the movie and presents an evaluation of four aggregation approaches. The evaluation demonstrates that the aggregation improves the accuracy of a centralized system containing the same ratings and proves the feasibility and advantages of a distributed collaborative filtering scenario.
---
paper_title: Personalized Communities in a Distributed Recommender System

paper_content:

The amount of data exponentially increases in information systems and it becomes more and more difficult to extract the most relevant information within a very short time. Among others, collaborative filtering processes help users to find interesting items by modeling their preferences and by comparing them with users having the same tastes. Nevertheless, there are a lot of aspects to consider when implementing such a recommender system. The number of potential users and the confidential nature of some data are taken into account. This paper introduces a new distributed recommender system based on a user-based filtering algorithm. Our model has been transposed for Peer-to-Peer architectures. It has been especially designed to deal with problems of scalability and privacy. Moreover, it adapts its prediction computations to the density of the user neighborhood.
---
paper_title: Distributed collaborative filtering for peer-to-peer file sharing systems

paper_content:

Collaborative filtering requires a centralized rating database. However, within a peer-to-peer network such a centralized database is not readily available. In this paper, we propose a fully distributed collaborative filtering method that is self-organizing and operates in a distributed way. Similarity ranks between multimedia files (items) are calculated by log-based user profiles and are stored locally at these items in so-called buddy tables. This intuitively creates a semantic overlay to organize multimedia files. Based on this semantic overlay and the items that a user has downloaded previously (indicating the profile of the user), recommendations can be performed and the recommended items can be easily located. We have tested our distributed collaborative filtering approach and compared it to centralized collaborative filtering, showing that it has similar performance. It is therefore a promising technique to facilitate filtering for relevant multimedia data in P2P networks.
---
paper_title: A Novel Distributed Collaborative Filtering Algorithm and Its Implementation on P2P Overlay Network

paper_content:

Collaborative filtering (CF) has proved to be one of the most effective information filtering techniques. However, as their calculation complexity increased quickly both in time and space when the record in user database increases, traditional centralized CF algorithms has suffered from their shortage in scalability. In this paper, we first propose a novel distributed CF algorithm called PipeCF through which we can do both the user database management and prediction task in a decentralized way. We then propose two novel approaches: significance refinement (SR) and unanimous amplification (UA), to further improve the scalability and prediction accuracy of PipeCF. Finally we give the algorithm framework and system architecture of the implementation of PipeCF on Peer-to-Peer (P2P) overlay network through distributed hash table (DHT) method, which is one of the most popular and effective routing algorithm in P2P. The experimental data show that our distributed CF algorithm has much better scalability than traditional centralized ones with comparable prediction efficiency and accuracy.
---
paper_title: DCFLA: A distributed collaborative-filtering neighbor-locating algorithm

paper_content:

Although collaborative filtering (CF) has proved to be one of the most successful techniques in recommendation systems, it suffers from a lack of scalability as the time complexity rapidly increases when the number of the records in the user database increases. As a result, distributed collaborative filtering (DCF) is attracting increasing attention as an alternative implementation scheme for CF-based recommendation systems. In this paper, we first propose a distributed user-profile management scheme using distributed hash table (DHT)-based routing algorithms, which is one of the most popular and effective approaches in peer-to-peer (P2P) overlay networks. In this DCF scheme, an efficient DCF neighbor-locating algorithm (DCFLA) is proposed, together with two improvements, most same opinion (MSO) and average rating normalization (ARN), to reduce the network traffic and time cost. Finally, we analyze the performance of one baseline and three novel CF algorithms are being proposed: (1) a traditional memory-based CF (baseline); (2) a basic DHT-based CF; (3) a DHT-based CF with MSO; and (4) a DHT-based CF with MSO and ARN. The experimental results show that the scalability of our proposed DCFLA is much better than the traditional centralized CF algorithm and the prediction accuracies of these two systems are comparable.
---
paper_title: Towards Fully Distributed and Privacy-Preserving Recommendations via Expert Collaborative Filtering and RESTful Linked Data

paper_content:

Expert Collaborative Filtering is an approach to recommender systems in which recommendations for users are derived from ratings coming from domain experts rather than peers. In this paper we present an implementation of this approach in the music domain. We show the applicability of the model in this setting, and show how it addresses many of the shortcomings in traditional Collaborative Filtering such as possible privacy concerns. We also describe a number of technologies and an architectural solution based on REST and the use of Linked Data that can be used to implement a completely distributed and privacy-preserving recommender system.
---
paper_title: A scalable P2P recommender system based on distributed collaborative filtering

paper_content:

Collaborative Filtering (CF) technique has been proved to be one of the most successful techniques in recommender systems in recent years. However, most existing CF based recommender systems worked in a centralized way and suffered from its shortage in scalability as their calculation complexity increased quickly both in time and space when the record in user database increases. In this article, we first propose a distributed CF algorithm called PipeCF together with two novel approaches: significance refinement and unanimous amplification, to further improve the scalability and prediction accuracy. We then show how to implement this algorithm on a Peer-to-Peer (P2P) structure through distributed hash table method, which is the most popular and efficient P2P routing algorithm, to construct a scalable distributed recommender system. The experimental data show that the distributed CF-based recommender system has much better scalability than traditional centralized ones with comparable prediction efficiency and accuracy. q 2004 Elsevier Ltd. All rights reserved.
---
paper_title: The wisdom of the few: a collaborative filtering approach based on expert opinions from the web

paper_content:

Nearest-neighbor collaborative filtering provides a successful means of generating recommendations for web users. However, this approach suffers from several shortcomings, including data sparsity and noise, the cold-start problem, and scalability. In this work, we present a novel method for recommending items to users based on expert opinions. Our method is a variation of traditional collaborative filtering: rather than applying a nearest neighbor algorithm to the user-rating data, predictions are computed using a set of expert neighbors from an independent dataset, whose opinions are weighted according to their similarity to the user. This method promises to address some of the weaknesses in traditional collaborative filtering, while maintaining comparable accuracy. We validate our approach by predicting a subset of the Netflix data set. We use ratings crawled from a web portal of expert reviews, measuring results both in terms of prediction accuracy and recommendation list precision. Finally, we explore the ability of our method to generate useful recommendations, by reporting the results of a user-study where users prefer the recommendations generated by our approach.
---
paper_title: A peer-to-peer recommender system based on spontaneous affinities

paper_content:

Network analysis has proved to be very useful in many social and natural sciences, and in particular Small World topologies have been exploited in many application fields. In this article, we focus on P2P file sharing applications, where spontaneous communities of users are studied and analyzed. We define a family of structures that we call “Affinity Networks” (or even Graphs) that show self-organized interest-based clusters. Empirical evidence proves that affinity networks are small worlds and shows scale-free features. The relevance of this finding is augmented with the introduction of a proactive recommendation scheme, namely DeHinter, that exploits this natural feature. The intuition behind this scheme is that a user would trust her network of “elective affinities” more than anonymous and generic suggestions made by impersonal entities. The accuracy of the recommendation is evaluated by way of a 10-fold cross validation, and a prototype has been implemented for further feedbacks from the users.
---
paper_title: Enhancing privacy and preserving accuracy of a distributed collaborative filtering

paper_content:

Collaborative Filtering (CF) is a powerful technique for generating personalized predictions. CF systems are typically based on a central storage of user profiles used for generating the recommendations. However, such centralized storage introduces a severe privacy breach, since the profiles may be accessed for purposes, possibly malicious, not related to the recommendation process. Recent researches proposed to protect the privacy of CF by distributing the profiles between multiple repositories and exchange only a subset of the profile data, which is useful for the recommendation. This work investigates how a decentralized distributed storage of user profiles combined with data modification techniques may mitigate some privacy issues. Results of experimental evaluation show that parts of the user profiles can be modified without hampering the accuracy of CF predictions. The experiments also indicate which parts of the user profiles are most useful for generating accurate CF predictions, while their exposure still keeps the essential privacy of the users.
---
paper_title: PocketLens: Toward a personal recommender system

paper_content:

Recommender systems using collaborative filtering are a popular technique for reducing information overload and finding products to purchase. One limitation of current recommenders is that they are not portable. They can only run on large computers connected to the Internet. A second limitation is that they require the user to trust the owner of the recommender with personal preference data. Personal recommenders hold the promise of delivering high quality recommendations on palmtop computers, even when disconnected from the Internet. Further, they can protect the user's privacy by storing personal information locally, or by sharing it in encrypted form. In this article we present the new PocketLens collaborative filtering algorithm along with five peer-to-peer architectures for finding neighbors. We evaluate the architectures and algorithms in a series of offline experiments. These experiments show that Pocketlens can run on connected servers, on usually connected workstations, or on occasionally connected portable devices, and produce recommendations that are as good as the best published algorithms to date.
---
paper_title: Improved recommendation systems

paper_content:

We consider a model of competitive recommendation systems proposed by Drineas et al. [4]. In recommendation systems (e.g., for books or movies), the system tracks which product each user chose in the past, and tries to deduce which other products an asking user is likely to be satisfied with. Obviously, recommendation systems can be effective only for users who share preferences with many other users. Such users are said to belong to a "dominant type." Current approaches to on-line recommendation systems involve using Singular Value Decomposition (SVD), which is computationally intensive and, more important, often applicable only under additional strong conditions. Specifically, correctness is guaranteed in [4] only if users of different dominant types essentially do not share a product they like ("type separability"), and only if the number of users in non-dominant types is significantly smaller than the number of users in dominant types ("gap assumption"). The complexity of that algorithm is O(mn), where m and n denote the number of users and products, respectively. In this paper, we show that in fact, very simple combinatorial algorithms can make good recommendations without using SVD. Our algorithms require neither the type separability nor the gap assumption, they are naturally amenable to distibuted computation, and their complexity is lower. In particular, the paper presents an O(m + n) time centralized algorithm and a distributed algorithm that can be implemented in a peer-to-peer model even in the presence of adaptively colluding malicious players, with only logarithmic over-head.
---
paper_title: Distributed user profiling via spectral methods

paper_content:

User profiling is a useful primitive for constructing personalised services, such as content recommendation. In the present paper we investigate the feasibility of user profiling in a distributed setting, with no central authority and only local information exchanges between users. We compute a profile vector for each user (i.e., a low-dimensional vector that characterises her taste) via spectral transformation of observed user-produced ratings for items. Our two main contributions follow: i) We consider a low-rank probabilistic model of user taste. More specifically, we consider that users and items are partitioned in a constant number of classes, such that users and items within the same class are statistically identical. We prove that without prior knowledge of the compositions of the classes, based solely on few random observed ratings (namely $O(N\log N)$ such ratings for $N$ users), we can predict user preference with high probability for unrated items by running a local vote among users with similar profile vectors. In addition, we provide empirical evaluations characterising the way in which spectral profiling performance depends on the dimension of the profile space. Such evaluations are performed on a data set of real user ratings provided by Netflix. ii) We develop distributed algorithms which provably achieve an embedding of users into a low-dimensional space, based on spectral transformation. These involve simple message passing among users, and provably converge to the desired embedding. Our method essentially relies on a novel combination of gossiping and the algorithm proposed by Oja and Karhunen.
---
paper_title: Decentralised Social Filtering based on Trust

paper_content:

This paper describes a decentralised approach to social filtering based on trust between agents in a multiagent system. The social filtering in the proposed approach is built on the interactions between collaborative software agents performing content-based filtering. This means that it uses a mixture of content-based and social filtering and thereby, it takes advantage of both methods.
---
paper_title: TiVo: making show recommendations using a distributed collaborative filtering architecture

paper_content:

We describe the TiVo television show collaborative recommendation system which has been fielded in over one million TiVo clients for four years. Over this install base, TiVo currently has approximately 100 million ratings by users over approximately 30,000 distinct TV shows and movies. TiVo uses an item-item (show to show) form of collaborative filtering which obviates the need to keep any persistent memory of each user's viewing preferences at the TiVo server. Taking advantage of TiVo's client-server architecture has produced a novel collaborative filtering system in which the server does a minimum of work and most work is delegated to the numerous clients. Nevertheless, the server-side processing is also highly scalable and parallelizable. Although we have not performed formal empirical evaluations of its accuracy, internal studies have shown its recommendations to be useful even for multiple user households. TiVo's architecture also allows for throttling of the server so if more server-side resources become available, more correlations can be computed on the server allowing TiVo to make recommendations for niche audiences.
---
paper_title: A Client/Server User-Based Collaborative Filtering Algorithm: Model and Implementation

paper_content:

This paper describes a new way of implementing an intelligent web caching service, based on an analysis of usage. Since the cache size in software is limited, and the search for new information is time-consuming, it becomes interesting to automate the process of selecting the most relevant items for each user. We propose a new generic model based on a client/server collaborative filtering algorithm and a behavior modeling process. In order to highlight the benefits of our solution, we collaborated with a company called ASTRA which is specialized in satellite website broadcasting. ASTRA has finalized a system sponsored by advertisement and supplying to users a high bandwidth access to hundreds of websites for free. Our work has been implemented within its software architecture and, in particular, within its recommender system in order to improve the satisfaction of users. Our solution is particularly designed to address the issues of data sparsity, privacy and scalability. Because of the industrial context, we consider the situation where the set of users is relatively stable, whereas the set of items may vary considerably from an execution to another. In addition to the model and its implementation, we present a performance assessment of our technique in terms of computation time and prediction relevancy.
---
paper_title: Large-Scale Parallel Collaborative Filtering for the Netflix Prize

paper_content:

Many recommendation systems suggest items to users by utilizing the techniques of collaborative filtering(CF) based on historical records of items that the users have viewed, purchased, or rated. Two major problems that most CF approaches have to contend with are scalability and sparseness of the user profiles. To tackle these issues, in this paper, we describe a CF algorithm alternating-least-squares with weighted-?-regularization(ALS-WR), which is implemented on a parallel Matlab platform. We show empirically that the performance of ALS-WR (in terms of root mean squared error(RMSE)) monotonically improves with both the number of features and the number of ALS iterations. We applied the ALS-WR algorithm on a large-scale CF problem, the Netflix Challenge, with 1000 hidden features and obtained a RMSE score of 0.8985, which is one of the best results based on a pure method. In addition, combining with the parallel version of other known methods, we achieved a performance improvement of 5.91% over Netflix's own CineMatch recommendation system. Our method is simple and scales well to very large datasets.
---
paper_title: Scalable co-clustering algorithms

paper_content:

Co-clustering has been extensively used in varied applications because of its potential to discover latent local patterns that are otherwise unapparent by usual unsupervised algorithms such as k-means Recently, a unified view of co-clustering algorithms, called Bregman co-clustering (BCC), provides a general framework that even contains several existing co-clustering algorithms, thus we expect to have more applications of this framework to varied data types However, the amount of data collected from real-life application domains easily grows too big to fit in the main memory of a single processor machine Accordingly, enhancing the scalability of BCC can be a critical challenge in practice To address this and eventually enhance its potential for rapid deployment to wider applications with larger data, we parallelize all the twelve co-clustering algorithms in the BCC framework using message passing interface (MPI) In addition, we validate their scalability on eleven synthetic datasets as well as one real-life dataset, where we demonstrate their speedup performance in terms of varied parameter settings.
---
paper_title: A generalized maximum entropy approach to bregman co-clustering and matrix approximation

paper_content:

Co-clustering, or simultaneous clustering of rows and columns of a two-dimensional data matrix, is rapidly becoming a powerful data analysis technique. Co-clustering has enjoyed wide success in varied application domains such as text clustering, gene-microarray analysis, natural language processing and image, speech and video analysis. In this paper, we introduce a partitional co-clustering formulation that is driven by the search for a good matrix approximation---every co-clustering is associated with an approximation of the original data matrix and the quality of co-clustering is determined by the approximation error. We allow the approximation error to be measured using a large class of loss functions called Bregman divergences that include squared Euclidean distance and KL-divergence as special cases. In addition, we permit multiple structurally different co-clustering schemes that preserve various linear statistics of the original data matrix. To accomplish the above tasks, we introduce a new minimum Bregman information (MBI) principle that simultaneously generalizes the maximum entropy and standard least squares principles, and leads to a matrix approximation that is optimal among all generalized additive models in a certain natural parameter space. Analysis based on this principle yields an elegant meta algorithm, special cases of which include most previously known alternate minimization based clustering algorithms such as kmeans and co-clustering algorithms such as information theoretic (Dhillon et al., 2003b) and minimum sum-squared residue co-clustering (Cho et al., 2004). To demonstrate the generality and flexibility of our co-clustering framework, we provide examples and empirical evidence on a variety of problem domains and also describe novel co-clustering applications such as missing value prediction and compression of categorical data matrices.
---
paper_title: A scalable collaborative filtering framework based on co-clustering

paper_content:

Collaborative filtering-based recommender systems have become extremely popular due to the increase in Web-based activities such as e-commerce and online content distribution. Current collaborative filtering (CF) techniques such as correlation and SVD based methods provide good accuracy, but are computationally expensive and can be deployed only in static off-line settings. However, a number of practical scenarios require dynamic real-time collaborative filtering that can allow new users, items and ratings to enter the system at a rapid rate. In this paper, we consider a novel CF approach based on a proposed weighted co-clustering algorithm (Banerjee et al., 2004) that involves simultaneous clustering of users and items. We design incremental and parallel versions of the co-clustering algorithm and use it to build an efficient real-time CF framework. Empirical evaluation demonstrates that our approach provides an accuracy comparable to that of the correlation and matrix factorization based approaches at a much lower computational cost.
---
paper_title: More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server

paper_content:

We propose a parameter server system for distributed ML, which follows a Stale Synchronous Parallel (SSP) model of computation that maximizes the time computational workers spend doing useful work on ML algorithms, while still providing correctness guarantees. The parameter server provides an easy-to-use shared interface for read/write access to an ML model's values (parameters and variables), and the SSP model allows distributed workers to read older, stale versions of these values from a local cache, instead of waiting to get them from a central storage. This significantly increases the proportion of time workers spend computing, as opposed to waiting. Furthermore, the SSP model ensures ML algorithm correctness by limiting the maximum age of the stale values. We provide a proof of correctness under SSP, as well as empirical results demonstrating that the SSP model achieves faster algorithm convergence on several different ML problems, compared to fully-synchronous and asynchronous schemes.
---
paper_title: Distributed Stochastic ADMM for Matrix Factorization

paper_content:

Matrix factorization (MF) has become the most popular technique for recommender systems due to its promising performance. Recently, distributed (parallel) MF models have received much attention from researchers of big data community. In this paper, we propose a novel model, called distributed stochastic alternating direction methods of multipliers (DS-ADMM), for large-scale MF problems. DS-ADMM is a distributed stochastic variant of ADMM. In particular, we first devise a new data split strategy to make the distributed MF problem fit for the ADMM framework. Then, a stochastic ADMM scheme is designed for learning. Finally, we implement DS-ADMM based on message passing interface (MPI), which can run on clusters with multiple machines (nodes). Experiments on several data sets from recommendation applications show that our DS-ADMM model can outperform other state-of-the-art distributed MF models in terms of both efficiency and accuracy.
---
paper_title: Application of Dimensionality Reduction in Recommender System -- A Case Study

paper_content:

Abstract : We investigate the use of dimensionality reduction to improve performance for a new class of data analysis software called "recommender systems" Recommender systems apply knowledge discovery techniques to the problem of making product recommendations during a live customer interaction. These systems are achieving widespread success in E-commerce nowadays, especially with the advent of the Internet. The tremendous growth of customers and products poses three key challenges for recommender systems in the E-commerce domain. These are: producing high quality recommendations, performing many recommendations per second for millions of customers and products, and achieving high coverage in the face of data sparsity. One successful recommender system technology is collaborative filtering, which works by matching customer preferences to other customers in making recommendations. Collaborative filtering has been shown to produce high quality recommendations, but the performance degrades with the number of customers and products. New recommender system technologies are needed that can quickly produce high quality recommendations, even for very largescale problems. This paper presents two different experiments where we have explored one technology called Singular Value Decomposition (SVD) to reduce the dimensionality of recommender system databases. Each experiment compares the quality of a recommender system using SVD with the quality of a recommender system using collaborative filtering. The first experiment compares the effectiveness of the two recommender systems at predicting consumer preferences based on a database of explicit ratings of products. The second experiment compares the effectiveness of the two recommender systems at producing Top-N lists based on a real-life customer purchase database from an E-Commerce site. Our experience suggests that SVD has the potential to meet many of the challenges of recommender systems, under certain conditions.
---
paper_title: High Performance Offline and Online Distributed Collaborative Filtering

paper_content:

Big data analytics is a hot research area both in academia and industry. It envisages processing massive amounts of data at high rates to generate new insights leading to positive impact (for both users and providers) of industries such as E-commerce, Telecom, Finance, Life Sciences and so forth. We consider collaborative filtering (CF) and Clustering algorithms that are key fundamental analytics kernels that help in achieving these aims. High throughput CF and co-clustering on highly sparse and massive datasets, along with a high prediction accuracy, is a computationally challenging problem. In this paper, we present a novel hierarchical design for soft real-time (less than 1-minute.) distributed co-clustering based collaborative filtering algorithm. We study both the online and offline variants of this algorithm. Theoretical analysis of the time complexity of our algorithm proves the efficacy of our approach. Further, we present the impact of load balancing based optimizations on multi-core cluster architectures. Using the Netflix dataset(900M training ratings with replication) as well as the Yahoo KDD Cup(2.3B training ratings with replication) datasets, we demonstrate the performance and scalability of our algorithm on a large multi-core cluster architecture. In offline mode, our distributed algorithm demonstrates around 4x better performance (on Blue Gene/P) as compared to the best prior work, along with high accuracy. In online mode, we demonstrated around 3x better performance compared to baseline MPI implementation. To the best of our knowledge, our algorithm provides the best known online and offline performance and scalability results with high accuracy on multi-core cluster architectures.
---
paper_title: Distributed scalable collaborative filtering algorithm

paper_content:

Collaborative filtering (CF) based recommender systems have gained wide popularity in Internet companies like Amazon, Netflix, Google News, and others. These systems make automatic predictions about the interests of a user by inferring from information about like-minded users. Real-time CF on highly sparse massive datasets, while achieving a high prediction accuracy, is a computationally challenging problem. In this paper, we present a novel design for soft real-time (less than 10 sec.) distributed co-clustering based Collaborative Filtering algorithm. Our distributed algorithm has been optimized for multi-core cluster architectures using pipelined parallelism, computation communication overlap and communication optimizations. Theoretical parallel time complexity analysis of our algorithm proves the efficacy of our approach. Using the Netflix dataset (100M ratings), we demonstrate the performance and scalability of our algorithm on 1024-node Blue Gene/P system. Our distributed algorithm (implemented using OpenMP with MPI) delivered training time of around 6s on the full Netflix dataset and prediction time of 2.5s on 1.4M ratings (1.78µs per rating prediction). Our training time is around 20× (more than one order of magnitude) better than the best known parallel training time, along with high accuracy (0.87±0.02 RMSE). To the best of our knowledge, this is the best known parallel performance for collaborative filtering on Netflix data at such high accuracy and also the first such implementation on multi-core cluster architectures such as Blue Gene/P.
---
paper_title: GroupLens: an open architecture for collaborative filtering of netnews

paper_content:

Collaborative filters help people make choices based on the opinions of other people. GroupLens is a system for collaborative filtering of netnews, to help people find articles they will like in the huge stream of available articles. News reader clients display predicted scores and make it easy for users to rate articles after they read them. Rating servers, called Better Bit Bureaus, gather and disseminate the ratings. The rating servers predict scores based on the heuristic that people who agreed in the past will probably agree again. Users can protect their privacy by entering ratings under pseudonyms, without reducing the effectiveness of the score prediction. The entire architecture is open: alternative software for news clients and Better Bit Bureaus can be developed independently and can interoperate with the components we have developed.
---
paper_title: Ranking via Robust Binary Classification

paper_content:

We propose RoBiRank, a ranking algorithm that is motivated by observing a close connection between evaluation metrics for learning to rank and loss functions for robust classification. It shows competitive performance on standard benchmark datasets against a number of other representative algorithms in the literature. We also discuss extensions of RoBiRank to large scale problems where explicit feature vectors and scores are not given. We show that RoBiRank can be efficiently parallelized across a large number of machines; for a task that requires 386,133 x 49,824, 519 pairwise interactions between items to be ranked, RoBiRank finds solutions that are of dramatically higher quality than that can be found by a state-of-the-art competitor algorithm, given the same amount of wall-clock time for computation.
---
paper_title: PLDA+: Parallel latent dirichlet allocation with data placement and pipeline processing

paper_content:

Previous methods of distributed Gibbs sampling for LDA run into either memory or communication bottlenecks. To improve scalability, we propose four strategies: data placement, pipeline processing, word bundling, and priority-based scheduling. Experiments show that our strategies significantly reduce the unparallelizable communication bottleneck and achieve good load balancing, and hence improve scalability of LDA.
---
paper_title: Distributed Matrix Completion

paper_content:

We discuss parallel and distributed algorithms for large-scale matrix completion on problems with millions of rows, millions of columns, and billions of revealed entries. We focus on in-memory algorithms that run on a small cluster of commodity nodes, even very large problems can be handled effectively in such a setup. Our DALS, ASGD, and DSGD++ algorithms are novel variants of the popular alternating least squares and stochastic gradient descent algorithms, they exploit thread-level parallelism, in-memory processing, and asynchronous communication. We provide some guidance on the asymptotic performance of each algorithm and investigate the performance of both our algorithms and previously proposed Map Reduce algorithms in large-scale experiments. We found that DSGD++ outperforms competing methods in terms of overall runtime, memory consumption, and scalability. Using DSGD++, we can factor a matrix with 10B entries on 16 compute nodes in around 40 minutes.
---
paper_title: Combinational collaborative filtering for personalized community recommendation

paper_content:

Rapid growth in the amount of data available on social networking sites has made information retrieval increasingly challenging for users. In this paper, we propose a collaborative filtering method, Combinational Collaborative Filtering (CCF), to perform personalized community recommendations by considering multiple types of co-occurrences in social data at the same time. This filtering method fuses semantic and user information, then applies a hybrid training strategy that combines Gibbs sampling and Expectation-Maximization algorithm. To handle the large-scale dataset, parallel computing is used to speed up the model training. Through an empirical study on the Orkut dataset, we show CCF to be both effective and scalable.
---
paper_title: Latent semantic models for collaborative filtering

paper_content:

Collaborative filtering aims at learning predictive models of user preferences, interests or behavior from community data, that is, a database of available user preferences. In this article, we describe a new family of model-based algorithms designed for this task. These algorithms rely on a statistical modelling technique that introduces latent class variables in a mixture model setting to discover user communities and prototypical interest profiles. We investigate several variations to deal with discrete and continuous response variables as well as with different objective functions. The main advantages of this technique over standard memory-based methods are higher accuracy, constant time prediction, and an explicit and compact model representation. The latter can also be used to mine for user communitites. The experimental evaluation shows that substantial improvements in accucracy over existing methods and published results can be obtained.
---
paper_title: Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems

paper_content:

Matrix factorization, when the matrix has missing values, has become one of the leading techniques for recommender systems. To handle web-scale datasets with millions of users and billions of ratings, scalability becomes an important issue. Alternating Least Squares (ALS) and Stochastic Gradient Descent (SGD) are two popular approaches to compute matrix factorization. There has been a recent flurry of activity to parallelize these algorithms. However, due to the cubic time complexity in the target rank, ALS is not scalable to large-scale datasets. On the other hand, SGD conducts efficient updates but usually suffers from slow convergence that is sensitive to the parameters. Coordinate descent, a classical optimization approach, has been used for many other large-scale problems, but its application to matrix factorization for recommender systems has not been explored thoroughly. In this paper, we show that coordinate descent based methods have a more efficient update rule compared to ALS, and are faster and have more stable convergence than SGD. We study different update sequences and propose the CCD++ algorithm, which updatesrank-one factors one by one. In addition, CCD++ can be easily parallelized on both multi-core and distributed systems. We empirically show that CCD++ is much faster than ALS and SGD in both settings. As an example, on a synthetic dataset with 2 billion ratings, CCD++ is 4 times faster than both SGD and ALS using a distributed system with 20 machines.
---
paper_title: Local collaborative ranking

paper_content:

Personalized recommendation systems are used in a wide variety of applications such as electronic commerce, social networks, web search, and more. Collaborative filtering approaches to recommendation systems typically assume that the rating matrix (e.g., movie ratings by viewers) is low-rank. In this paper, we examine an alternative approach in which the rating matrix is locally low-rank. Concretely, we assume that the rating matrix is low-rank within certain neighborhoods of the metric space defined by (user, item) pairs. We combine a recent approach for local low-rank approximation based on the Frobenius norm with a general empirical risk minimization for ranking losses. Our experiments indicate that the combination of a mixture of local low-rank matrices each of which was trained to minimize a ranking loss outperforms many of the currently used state-of-the-art recommendation systems. Moreover, our method is easy to parallelize, making it a viable approach for large scale real-world rank-based recommendation systems.
---
paper_title: Large-scale matrix factorization with distributed stochastic gradient descent

paper_content:

We provide a novel algorithm to approximately factor large matrices with millions of rows, millions of columns, and billions of nonzero elements. Our approach rests on stochastic gradient descent (SGD), an iterative stochastic optimization algorithm. We first develop a novel "stratified" SGD variant (SSGD) that applies to general loss-minimization problems in which the loss function can be expressed as a weighted sum of "stratum losses." We establish sufficient conditions for convergence of SSGD using results from stochastic approximation theory and regenerative process theory. We then specialize SSGD to obtain a new matrix-factorization algorithm, called DSGD, that can be fully distributed and run on web-scale datasets using, e.g., MapReduce. DSGD can handle a wide variety of matrix factorizations. We describe the practical techniques used to optimize performance in our DSGD implementation. Experiments suggest that DSGD converges significantly faster and has better scalability properties than alternative algorithms.
---
paper_title: Multithreaded Implementation of the Slope One Algorithm for Collaborative Filtering

paper_content:

Recommender systems are mechanisms that filter information and predict a user’s preference to an item. Parallel implementations of recommender systems improve scalability issues and can be applied to internet-based companies having considerable impact on their profits. This paper implements a parallel version of the collaborative filtering algorithm Slope One, which has advantages such as its efficiency and the ability to update data dynamically. The presented version is parallely implemented with the use of the OpenMP API and its performance is evaluated on a multi-core system.
---
paper_title: A zealous parallel gradient descent algorithm

paper_content:

Parallel and distributed algorithms have become a necessity in modern machine learning tasks. In this work, we focus on parallel asynchronous gradient descent [1, 2, 3] and propose a zealous variant that minimizes the idle time of processors to achieve a substantial speedup. We then experimentally study this algorithm in the context of training a restricted Boltzmann machine on a large collaborative filtering task.
---
paper_title: Highly scalable parallel collaborative filtering algorithm

paper_content:

Collaborative filtering (CF) based recommender systems have gained wide popularity in Internet companies like Amazon, Netflix, Google News, and others. These systems make automatic predictions about the interests of a user by inferring from information about like-minded users. Realtime CF on highly sparse massive datasets, while achieving a high prediction accuracy, is a computationally challenging problem. In this paper, we present the design of a soft real-time (around 1 min.) parallel CF algorithm based on the Concept Decomposition technique [1]. Our parallel algorithm has been optimized for multicore/many-core architectures while maintaining the prediction accuracy of 0.84 RMSE. Using the Netflix dataset, we demonstrate the performance and scalability of our algorithm (in both batch mode and online mode) on a 32-core Power6 based SMP system. Our parallel algorithm delivered training time of 64s on the full Netflix dataset and prediction time of 4.5s on IAM ratings (3.2/μs per rating prediction). This is 12.6× better than the best known sequential training time and around 33 × better than the best known sequential prediction time [2], along with high accuracy (Ό.84 RMSE). To the best of our knowledge, this is also the best known parallel performance at such high accuracy.
---
paper_title: A fast parallel SGD for matrix factorization in shared memory systems

paper_content:

Matrix factorization is known to be an effective method for recommender systems that are given only the ratings from users to items. Currently, stochastic gradient descent (SGD) is one of the most popular algorithms for matrix factorization. However, as a sequential approach, SGD is difficult to be parallelized for handling web-scale problems. In this paper, we develop a fast parallel SGD method, FPSGD, for shared memory systems. By dramatically reducing the cache-miss rate and carefully addressing the load balance of threads, FPSGD is more efficient than state-of-the-art parallel algorithms for matrix factorization.
---
paper_title: Extending average precision to graded relevance judgments

paper_content:

Evaluation metrics play a critical role both in the context of comparative evaluation of the performance of retrieval systems and in the context of learning-to-rank (LTR) as objective functions to be optimized. Many different evaluation metrics have been proposed in the IR literature, with average precision (AP) being the dominant one due a number of desirable properties it possesses. However, most of these measures, including average precision, do not incorporate graded relevance. In this work, we propose a new measure of retrieval effectiveness, the Graded Average Precision (GAP). GAP generalizes average precision to the case of multi-graded relevance and inherits all the desirable characteristics of AP: it has a nice probabilistic interpretation, it approximates the area under a graded precision-recall curve and it can be justified in terms of a simple but moderately plausible user model. We then evaluate GAP in terms of its informativeness and discriminative power. Finally, we show that GAP can reliably be used as an objective metric in learning to rank by illustrating that optimizing for GAP using SoftRank and LambdaRank leads to better performing ranking functions than the ones constructed by algorithms tuned to optimize for AP or NDCG even when using AP or NDCG as the test metrics.
---
paper_title: Localized matrix factorization for recommendation based on matrix block diagonal forms

paper_content:

Matrix factorization on user-item rating matrices has achieved significant success in collaborative filtering based recommendation tasks. However, it also encounters the problems of data sparsity and scalability when applied in real-world recommender systems. In this paper, we present the Localized Matrix Factorization (LMF) framework, which attempts to meet the challenges of sparsity and scalability by factorizing Block Diagonal Form (BDF) matrices. In the LMF framework, a large sparse matrix is first transformed into Recursive Bordered Block Diagonal Form (RBBDF), which is an intuitionally interpretable structure for user-item rating matrices. Smaller and denser submatrices are then extracted from this RBBDF matrix to construct a BDF matrix for more effective collaborative prediction. We show formally that the LMF framework is suitable for matrix factorization and that any decomposable matrix factorization algorithm can be integrated into this framework. It has the potential to improve prediction accuracy by factorizing smaller and denser submatrices independently, which is also suitable for parallelization and contributes to system scalability at the same time. Experimental results based on a number of real-world public-access benchmarks show the effectiveness and efficiency of the proposed LMF framework.
---
paper_title: Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems

paper_content:

Matrix factorization, when the matrix has missing values, has become one of the leading techniques for recommender systems. To handle web-scale datasets with millions of users and billions of ratings, scalability becomes an important issue. Alternating Least Squares (ALS) and Stochastic Gradient Descent (SGD) are two popular approaches to compute matrix factorization. There has been a recent flurry of activity to parallelize these algorithms. However, due to the cubic time complexity in the target rank, ALS is not scalable to large-scale datasets. On the other hand, SGD conducts efficient updates but usually suffers from slow convergence that is sensitive to the parameters. Coordinate descent, a classical optimization approach, has been used for many other large-scale problems, but its application to matrix factorization for recommender systems has not been explored thoroughly. In this paper, we show that coordinate descent based methods have a more efficient update rule compared to ALS, and are faster and have more stable convergence than SGD. We study different update sequences and propose the CCD++ algorithm, which updatesrank-one factors one by one. In addition, CCD++ can be easily parallelized on both multi-core and distributed systems. We empirically show that CCD++ is much faster than ALS and SGD in both settings. As an example, on a synthetic dataset with 2 billion ratings, CCD++ is 4 times faster than both SGD and ALS using a distributed system with 20 machines.
---
paper_title: Solving k-Nearest Neighbor Problem on Multiple Graphics Processors

paper_content:

A recommendation system is a software system to predict customers' unknown preferences from known preferences. In a recommendation system, customers' preferences are encoded into vectors, and finding the nearest vectors to each vector is an essential part. This vector-searching part of the problem is called a $k$-nearest neighbor problem. We give an effective algorithm to solve this problem on multiple graphics processor units (GPUs). Our algorithm consists of two parts: an $N$-body problem and a partial sort. For a algorithm of the $N$-body problem, we applied the idea of a known algorithm for the $N$-body problem in physics, although another trick is need to overcome the problem of small sized shared memory. For the partial sort, we give a novel GPU algorithm which is effective for small $k$. In our partial sort algorithm, a heap is accessed in parallel by threads with a low cost of synchronization. Both of these two parts of our algorithm utilize maximal power of coalesced memory access, so that a full bandwidth is achieved. By an experiment, we show that when the size of the problem is large, an implementation of the algorithm on two GPUs runs more than 330 times faster than a single core implementation on a latest CPU. We also show that our algorithm scales well with respect to the number of GPUs.
---
paper_title: Optimizing a Collaborative Filtering Recommender for Many-Core Processors

paper_content:

The web is moving from an era of "search" to that of "discovery". Collaborative filtering (CF) recommender systems are now commonly used to predict user's preference towards an unknown item from past ratings. To be scalable or effective, they are typically deployed in distributed clusters and operate on extremely large apriori datasets. Improvement of the efficiency of these systems is increasingly recognized important and challenging. Meanwhile, emerging many-core processors present an opportunity to optimize these systems on a per-node basis. We identify and address challenges in fast computation of correlations by maximizing data locality and minimizing communication cost between individual cores. We experiment run-time, power and energy consumed on: (1) Intel's experimental single chip cloud computer (SCC), (2) NVIDIA's CUDA-enabled GPGPU co-processor and (3) traditional server class x86 processor. We achieve super linear speedups (~30x), reduction in energy consumption (~90%) for benchmark workloads. Introduction of this design in CF systems can significantly reduce the number of servers required in a data center, energy consumption, operation costs and floor area bringing in significant savings.
---
paper_title: A social network-aware top-N recommender system using GPU

paper_content:

A book recommender system is very useful for a digital library. Good book recommender systems can effectively help users find interesting and relevant books from the massive resources, by providing individual recommendation book list for each end-user. By now, a variety of collaborative filtering algorithms have been invented, which are the cores of most recommender systems. However, because of the explosion of information, especially in the Internet, the improvement of the efficiency of the collaborative filting (CF) algorithm becomes more and more important. In this paper, we first propose a parallel Top-N recommendation algorithm in CUDA (Compute Unified Device Architecture) which combines the collaborative filtering and trust-based approach to deal with the cold-start user problem. Then based on this algorithm, we present a parallel book recommender system on a GPU (Graphics Processor unit) for CADAL digital library platform. Our experimental results show our algorithm is very efficient to process the large-scale datasets with good accuracy, and we report the impact of different values of parameters on the recommendation performance.
---
paper_title: Restricted Boltzmann machines for collaborative filtering

paper_content:

Most of the existing approaches to collaborative filtering cannot handle very large data sets. In this paper we show how a class of two-layer undirected graphical models, called Restricted Boltzmann Machines (RBM's), can be used to model tabular data, such as user's ratings of movies. We present efficient learning and inference procedures for this class of models and demonstrate that RBM's can be successfully applied to the Netflix data set, containing over 100 million user/movie ratings. We also show that RBM's slightly outperform carefully-tuned SVD models. When the predictions of multiple RBM models and multiple SVD models are linearly combined, we achieve an error rate that is well over 6% better than the score of Netflix's own system.
---
paper_title: Non-parametric co-clustering of large scale sparse bipartite networks on the GPU

paper_content:

Co-clustering is a problem of both theoretical and practical importance, e.g., market basket analysis and collaborative filtering, and in web scale text processing. We state the co-clustering problem in terms of non-parametric generative models which can address the issue of estimating the number of row and column clusters from a hypothesis space of an infinite number of clusters. To reach large scale applications of co-clustering we exploit that parameter inference for co-clustering is well suited for parallel computing. We develop a generic GPU framework for efficient inference on large scale sparse bipartite networks and achieve a speedup of two orders of magnitude compared to estimation based on conventional CPUs. In terms of scalability we find for networks with more than 100 million links that reliable inference can be achieved in less than an hour on a single GPU. To efficiently manage memory consumption on the GPU we exploit the structure of the posterior likelihood to obtain a decomposition that easily allows model estimation of the co-clustering problem on arbitrary large networks as well as distributed estimation on multiple GPUs. Finally we evaluate the implementation on real-life large scale collaborative filtering data and web scale text corpora, demonstrating that latent mesoscale structures extracted by the co-clustering problem as formulated by the Infinite Relational Model (IRM) are consistent across consecutive runs with different initializations and also relevant for interpretation of the underlaying processes in such large scale networks.
---
paper_title: Dogwild! – Distributed Hogwild for CPU & GPU

paper_content:

Deep learning has enjoyed tremendous success in recent years. Unfortunately, training large models can be very time consuming, even on GPU hardware. We describe a set of extensions to the state of the art Caffe library [3], allowing training on multiple threads and GPUs, and across multiple machines. Our focus is on architecture, implementing asynchronous SGD without increasing Caffe’s complexity. We isolate parallelization from Caffe’s existing SGD code, train unmodified models, and run on commodity hardware. Isolation is achieved by extending the Hogwild model, i.e. running parallel SGD solvers without synchronization, by also removing synchronization between solvers and components in charge of streaming gradients between nodes. In this modular design, components interact exclusively through unsynchronized reads and writes to the weight buffer. Each component is free to loop over the weights at a different pace, keeping both compute and network resources fully utilized. SGD’s resiliency against gradient loss allows further performance improvements by avoiding reliable network protocols. It enables the use of multicast messages, and of low level packets streaming through raw sockets or InfiniBand verbs. We show linear performance scaling for small clusters on MNIST, and early results on ImageNet.
---
paper_title: GPU-accelerated restricted boltzmann machine for collaborative filtering

paper_content:

Collaborative Filtering (CF) is an important technique for recommendation systems which model and analyzes the preferences of customers for giving reasonable advices. Recently, many applications based on Restricted Boltzmann Machine (RBM) have been developed for a large variety of learning problems. RBM-based model for Collaborative Filtering (RBM-CF) is able to deal with large scale data sets and obtains good recommendation performance. However, the computation of RBM becomes problematic when using large number of hidden features to improve the recommendation accuracy. Although RBM has great potential for parallelism, it is still a challenge to develop a parallel implementation of RBM-CF on GPU, since the data sets for CF are always large and sparse. In this paper, we propose a parallel implementation of RBM-CF on GPU using CUDA. We first present how to transform the computation of RBM-CF into matrix-based operation on GPU, and three CUDA kernels for sparse matrix-matrix multiplication to further improve the computational efficiency of RBM-CF for modeling large scale and sparse data sets. Experimental results show that significant speedups are achieved by our parallel implementation on GPU.
---
paper_title: Stochastic gradient descent with GPGPU

paper_content:

We show how to optimize a Support Vector Machine and a predictor for Collaborative Filtering with Stochastic Gradient Descent on the GPU, achieving 1.66 to 6-times accelerations compared to a CPU-based implementation. The reference implementations are the Support Vector Machine by Bottou and the BRISMF predictor from the Netflix Prices winning team. Our main idea is to create a hash function of the input data and use it to execute threads in parallel that write on different elements of the parameter vector. We also compare the iterative optimization with a batch gradient descent and an alternating least squares optimization. The predictor is tested against over a hundred million data sets which demonstrates the increasing memory management capabilities of modern GPUs. We make use of matrix as well as float compression to alleviate the memory bottleneck.
---
paper_title: QUIC-SVD: Fast SVD Using Cosine Trees

paper_content:

The Singular Value Decomposition is a key operation in many machine learning methods. Its computational cost, however, makes it unscalable and impractical for applications involving large datasets or real-time responsiveness, which are becoming increasingly common. We present a new method, QUIC-SVD, for fast approximation of the whole-matrix SVD based on a new sampling mechanism called the cosine tree. Our empirical tests show speedups of several orders of magnitude over exact SVD. Such scalability should enable QUIC-SVD to accelerate and enable a wide array of SVD-based methods and applications.
---
paper_title: A GPU-based Approximate SVD Algorithm

paper_content:

Approximation of matrices using the Singular Value Decomposition (SVD) plays a central role in many science and engineering applications. However, the computation cost of an exact SVD is prohibitively high for very large matrices. In this paper, we describe a GPU-based approximate SVD algorithm for large matrices. Our method is based on the QUIC-SVD introduced by [6], which exploits a tree-based structure to efficiently discover a subset of rows that spans the matrix space. We describe how to map QUIC-SVD onto the GPU, and improve its speed and stability using a blocked Gram-Schmidt orthogonalization method. Using a simple matrix partitioning scheme, we have extended our algorithm to out-of-core computation, suitable for very large matrices that exceed the main memory size. Results show that our GPU algorithm achieves 6˜7 times speedup over an optimized CPU version of QUIC-SVD, which itself is orders of magnitude faster than exact SVD methods.
---
paper_title: Singular value decomposition for collaborative filtering on a GPU

paper_content:

A collaborative filtering predicts customers' unknown preferences from known preferences. In a computation of the collaborative filtering, a singular value decomposition (SVD) is needed to reduce the size of a large scale matrix so that the burden for the next phase computation will be decreased. In this application, SVD means a roughly approximated factorization of a given matrix into smaller sized matrices. Webb (a.k.a. Simon Funk) showed an effective algorithm to compute SVD toward a solution of an open competition called "Netflix Prize". The algorithm utilizes an iterative method so that the error of approximation improves in each step of the iteration. We give a GPU version of Webb's algorithm. Our algorithm is implemented in the CUDA and it is shown to be efficient by an experiment.
---
paper_title: User-Based Collaborative-Filtering Recommendation Algorithms on Hadoop

paper_content:

Collaborative Filtering(CF) algorithms are widely used in a lot of recommender systems, however, the computational complexity of CF is high thus hinder their use in large scale systems. In this paper, we implement user-based CF algorithm on a cloud computing platform, namely Hadoop, to solve the scalability problem of CF. Experimental results show that a simple method that partition users into groups according to two basic principles, i.e., tidy arrangement of mapper number to overcome the initiation of mapper and partition task equally such that all processors finish task at the same time, can achieve linear speedup.
---
paper_title: Google news personalization: scalable online collaborative filtering

paper_content:

Several approaches to collaborative filtering have been studied but seldom have studies been reported for large (several millionusers and items) and dynamic (the underlying item set is continually changing) settings. In this paper we describe our approach to collaborative filtering for generating personalized recommendations for users of Google News. We generate recommendations using three approaches: collaborative filtering using MinHash clustering, Probabilistic Latent Semantic Indexing (PLSI), and covisitation counts. We combine recommendations from different algorithms using a linear model. Our approach is content agnostic and consequently domain independent, making it easily adaptable for other applications and languages with minimal effort. This paper will describe our algorithms and system setup in detail, and report results of running the recommendations engine on Google News.
---
paper_title: Scalable similarity-based neighborhood methods with MapReduce

paper_content:

Similarity-based neighborhood methods, a simple and popular approach to collaborative filtering, infer their predictions by finding users with similar taste or items that have been similarly rated. If the number of users grows to millions, the standard approach of sequentially examining each item and looking at all interacting users does not scale. To solve this problem, we develop a MapReduce algorithm for the pairwise item comparison and top-N recommendation problem that scales linearly with respect to a growing number of users. This parallel algorithm is able to work on partitioned data and is general in that it supports a wide range of similarity measures. We evaluate our algorithm on a large dataset consisting of 700 million song ratings from Yahoo! Music.
---
paper_title: Parallel User Profiling Based on Folksonomy for Large Scaled Recommender Systems: An Implimentation of Cascading MapReduce

paper_content:

The Large scaled emerging user created information in web 2.0 such as tags, reviews, comments and blogs can be used to profile users' interests and preferences to make personalized recommendations. To solve the scalability problem of the current user profiling and recommender systems, this paper proposes a parallel user profiling approach and a scalable recommender system. The current advanced cloud computing techniques including Hadoop, MapReduce and Cascading are employed to implement the proposed approaches. The experiments were conducted on Amazon EC2 Elastic MapReduce and S3 with a real world large scaled dataset from Del.icio.us website. 4 , it becomes easy and convenient for general users with little or no cloud computing knowledge to implement and run customer applications with large scaled datasets on clouds quickly. In this paper, we propose a parallel user profiling approach based on folksonomy information using the advanced cloud computing techniques. In addition, a paralleled scalable recommender system implemented based on Cascading MapReduce is also proposed. This paper is organized as follows. Firstly, the related work is briefly reviewed in Section II. Then, some important definitions are given in Section III. The proposed approaches are discussed in Section IV, where the parallel user profiling and recommendation making approaches designed based on Cascading MapReduce are presented. In Section V, the design of the experiments, experimental results and discussions are presented. The conclusions and future work are discussed in Section VI.
---
paper_title: The YouTube video recommendation system

paper_content:

We discuss the video recommendation system in use at YouTube, the world's most popular online video community. The system recommends personalized sets of videos to users based on their activity on the site. We discuss some of the unique challenges that the system faces and how we address them. In addition, we provide details on the experimentation and evaluation framework used to test and tune new algorithms. We also present some of the findings from these experiments.
---
paper_title: Distributed collaborative filtering with singular ratings for large scale recommendation

paper_content:

Collaborative filtering (CF) is an effective technique addressing the information overloading problem, where each user is associated with a set of rating scores on a set of items. For a chosen target user, conventional CF algorithms measure similarity between this user and other users by utilizing pairs of rating scores on common rated items, but discarding scores rated by one of them only. We call these comparative scores as dual ratings, while the non-comparative scores as singular ratings. Our experiments show that only about 10% ratings are dual ones that can be used for similarity evaluation, while the other 90% are singular ones. In this paper, we propose SingCF approach, which attempts to incorporate multiple singular ratings, in addition to dual ratings, to implement collaborative filtering, aiming at improving the recommendation accuracy. We first estimate the unrated scores for singular ratings and transform them into dual ones. Then we perform a CF process to discover neighborhood users and make predictions for each target user. Furthermore, we provide a MapReduce-based distributed framework on Hadoop for significant improvement in efficiency. Experiments in comparison with the state-of-the-art methods demonstrate the performance gains of our approaches.
---
paper_title: Clustering Weighted Slope One for distributed parallel computing

paper_content:

Slope One is a simple and widely used collective filter algorithm, it is easy to implemented and works effectively. After Slope One being published, some optimized Slope One algorithms were proposed for improving its accuracy, however these optimized algorithms still overlook some essential drawbacks of Slope One: oversize calculating set. This paper proposes an optimized Slope One which adapts clustering concept to conventional Slope One.
---
paper_title: Generalized Low Rank Models

paper_content:

Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types. This framework encompasses many well known techniques in data analysis, such as nonnegative matrix factorization, matrix completion, sparse and robust PCA, $k$-means, $k$-SVD, and maximum margin matrix factorization. The method handles heterogeneous data sets, and leads to coherent schemes for compressing, denoising, and imputing missing entries across all data types simultaneously. It also admits a number of interesting interpretations of the low rank factors, which allow clustering of examples or of features. We propose several parallel algorithms for fitting generalized low rank models, and describe implementations and numerical results.
---
paper_title: Large-scale matrix factorization with distributed stochastic gradient descent

paper_content:

We provide a novel algorithm to approximately factor large matrices with millions of rows, millions of columns, and billions of nonzero elements. Our approach rests on stochastic gradient descent (SGD), an iterative stochastic optimization algorithm. We first develop a novel "stratified" SGD variant (SSGD) that applies to general loss-minimization problems in which the loss function can be expressed as a weighted sum of "stratum losses." We establish sufficient conditions for convergence of SSGD using results from stochastic approximation theory and regenerative process theory. We then specialize SSGD to obtain a new matrix-factorization algorithm, called DSGD, that can be fully distributed and run on web-scale datasets using, e.g., MapReduce. DSGD can handle a wide variety of matrix factorizations. We describe the practical techniques used to optimize performance in our DSGD implementation. Experiments suggest that DSGD converges significantly faster and has better scalability properties than alternative algorithms.
---
paper_title: Scaling matrix factorization for recommendation with randomness

paper_content:

Recommendation is one of the core problems in eCommerce. In our application, different from conventional collaborative filtering, one user can engage in various types of activities in a sequence. Meanwhile, the number of users and items involved are quite huge, entailing scalable approaches. In this paper, we propose one simple approach to integrate multiple types of user actions for recommendation. A two-stage randomized matrix factorization is presented to handle large-scale collaborative filtering where alternating least squares or stochastic gradient descent is not viable. Empirical results show that the method is quite scalable, and is able to effectively capture correlations between different actions, thus making more relevant recommendations.
---
paper_title: MLI: An API for Distributed Machine Learning

paper_content:

MLI is an Application Programming Interface designed to address the challenges of building Machine Learning algorithms in a distributed setting based on data-centric computing. Its primary goal is to simplify the development of high-performance, scalable, distributed algorithms. Our initial results show that, relative to existing systems, this interface can be used to build distributed implementations of a wide variety of common Machine Learning algorithms with minimal complexity and highly competitive performance and scalability.
---
paper_title: Supercharging Recommender Systems using Taxonomies for Learning User Purchase Behavior

paper_content:

Recommender systems based on latent factor models have been effectively used for understanding user interests and predicting future actions. Such models work by projecting the users and items into a smaller dimensional space, thereby clustering similar users and items together and subsequently compute similarity between unknown user-item pairs. When user-item interactions are sparse (sparsity problem) or when new items continuously appear (cold start problem), these models perform poorly. In this paper, we exploit the combination of taxonomies and latent factor models to mitigate these issues and improve recommendation accuracy. We observe that taxonomies provide structure similar to that of a latent factor model: namely, it imposes human-labeled categories (clusters) over items. This leads to our proposed taxonomy-aware latent factor model (TF) which combines taxonomies and latent factors using additive models. We develop efficient algorithms to train the TF models, which scales to large number of users/items and develop scalable inference/recommendation algorithms by exploiting the structure of the taxonomy. In addition, we extend the TF model to account for the temporal dynamics of user interests using highorder Markov chains. To deal with large-scale data, we develop a parallel multi-core implementation of our TF model. We empirically evaluate the TF model for the task of predicting user purchases using a real-world shopping dataset spanning more than a million users and products. Our experiments demonstrate the benefits of using our TF models over existing approaches, in terms of both prediction accuracy and running time.
---
paper_title: Sparkler: supporting large-scale matrix factorization

paper_content:

Low-rank matrix factorization has recently been applied with great success on matrix completion problems for applications like recommendation systems, link predictions for social networks, and click prediction for web search. However, as this approach is applied to increasingly larger datasets, such as those encountered in web-scale recommender systems like Netflix and Pandora, the data management aspects quickly become challenging and form a road-block. In this paper, we introduce a system called Sparkler to solve such large instances of low rank matrix factorizations. Sparkler extends Spark, an existing platform for running parallel iterative algorithms on datasets that fit in the aggregate main memory of a cluster. Sparkler supports distributed stochastic gradient descent as an approach to solving the factorization problem -- an iterative technique that has been shown to perform very well in practice. We identify the shortfalls of Spark in solving large matrix factorization problems, especially when running on the cloud, and solve this by introducing a novel abstraction called "Carousel Maps" (CMs). CMs are well suited to storing large matrices in the aggregate memory of a cluster and can efficiently support the operations performed on them during distributed stochastic gradient descent. We describe the design, implementation, and the use of CMs in Sparkler programs. Through a variety of experiments, we demonstrate that Sparkler is faster than Spark by 4x to 21x, with bigger advantages for larger problems. Equally importantly, we show that this can be done without imposing any changes to the ease of programming. We argue that Sparkler provides a convenient and efficient extension to Spark for solving matrix factorization problems on very large datasets.
---
paper_title: Pervasive parallelism in data mining: dataflow solution to co-clustering large and sparse Netflix data

paper_content:

All Netflix Prize algorithms proposed so far are prohibitively costly for large-scale production systems. In this paper, we describe an efficient dataflow implementation of a collaborative filtering (CF) solution to the Netflix Prize problem [1] based on weighted coclustering [5]. The dataflow library we use facilitates the development of sophisticated parallel programs designed to fully utilize commodity multicore hardware, while hiding traditional difficulties such as queuing, threading, memory management, and deadlocks. The dataflow CF implementation first compresses the large, sparse training dataset into co-clusters. Then it generates recommendations by combining the average ratings of the co-clusters with the biases of the users and movies. When configured to identify 20x20 co-clusters in the Netflix training dataset, the implementation predicted over 100 million ratings in 16.31 minutes and achieved an RMSE of 0.88846 without any fine-tuning or domain knowledge. This is an effective real-time prediction runtime of 9.7 us per rating which is far superior to previously reported results. Moreover, the implemented co-clustering framework supports a wide variety of other large-scale data mining applications and forms the basis for predictive modeling on large, dyadic datasets [4, 7].
---
paper_title: Parallelized stochastic gradient descent

paper_content:

With the increase in available data parallel machine learning has become an increasingly pressing problem. In this paper we present the first parallel stochastic gradient descent algorithm including a detailed analysis and experimental evidence. Unlike prior work on parallel optimization algorithms [5, 7] our variant comes with parallel acceleration guarantees and it poses no overly tight latency constraints, which might only be available in the multicore setting. Our analysis introduces a novel proof technique — contractive mappings to quantify the speed of convergence of parameter distributions to their asymptotic limits. As a side effect this answers the question of how quickly stochastic gradient descent algorithms reach the asymptotically normal regime [1, 8].
---
paper_title: Distributed matrix factorization with mapreduce using a series of broadcast-joins

paper_content:

The efficient, distributed factorization of large matrices on clusters of commodity machines is crucial to applying latent factor models in industrial-scale recommender systems. We propose an efficient, data-parallel low-rank matrix factorization with Alternating Least Squares which uses a series of broadcast-joins that can be efficiently executed with MapReduce. We empirically show that the performance of our solution is suitable for real-world use cases. We present experiments on two publicly available datasets and on a synthetic dataset termed Bigflix, generated from the Netflix dataset. Bigflix contains 25 million users and more than 5 billion ratings, mimicking data sizes recently reported as Netflix' production workload. We demonstrate that our approach is able to run an iteration of Alternating Least Squares in six minutes on this dataset. Our implementation has been contributed to the open source machine learning library Apache Mahout.
---
paper_title: Generalized Low Rank Models

paper_content:

Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types. This framework encompasses many well known techniques in data analysis, such as nonnegative matrix factorization, matrix completion, sparse and robust PCA, $k$-means, $k$-SVD, and maximum margin matrix factorization. The method handles heterogeneous data sets, and leads to coherent schemes for compressing, denoising, and imputing missing entries across all data types simultaneously. It also admits a number of interesting interpretations of the low rank factors, which allow clustering of examples or of features. We propose several parallel algorithms for fitting generalized low rank models, and describe implementations and numerical results.
---
paper_title: Factorbird - a Parameter Server Approach to Distributed Matrix Factorization

paper_content:

We present Factorbird, a prototype of a parameter server approach for factorizing large matrices with Stochastic Gradient Descent-based algorithms. We designed Factorbird to meet the following desiderata: (a) scalability to tall and wide matrices with dozens of billions of non-zeros, (b) extensibility to different kinds of models and loss functions as long as they can be optimized using Stochastic Gradient Descent (SGD), and (c) adaptability to both batch and streaming scenarios. Factorbird uses a parameter server in order to scale to models that exceed the memory of an individual machine, and employs lock-free Hogwild!-style learning with a special partitioning scheme to drastically reduce conflicting updates. We also discuss other aspects of the design of our system such as how to efficiently grid search for hyperparameters at scale. We present experiments of Factorbird on a matrix built from a subset of Twitter's interaction graph, consisting of more than 38 billion non-zeros and about 200 million rows and columns, which is to the best of our knowledge the largest matrix on which factorization results have been reported in the literature.
---
paper_title: Multithreaded Implementation of the Slope One Algorithm for Collaborative Filtering

paper_content:

Recommender systems are mechanisms that filter information and predict a user’s preference to an item. Parallel implementations of recommender systems improve scalability issues and can be applied to internet-based companies having considerable impact on their profits. This paper implements a parallel version of the collaborative filtering algorithm Slope One, which has advantages such as its efficiency and the ability to update data dynamically. The presented version is parallely implemented with the use of the OpenMP API and its performance is evaluated on a multi-core system.
---
paper_title: Semi-sparse algorithm based on multi-layer optimization for recommendation system

paper_content:

Collaborative filter (CF) is the most successful technique in recommender system, which makes personalize recommendations during online interaction. We propose a new Semi-sparse algorithm based on multi-layer optimization to speed up the basic Pearson Correlation Coefficient of CF. Semi-sparse algorithm spares out over-reduplicate accessing and judgement on selected sparse vector to accelerate the batch of similarity-comparisons in one thread. We propose a reduce-vector in thread-pool to restrict the lock using on critical resources in parallelize implementation. Thread-pool is wrapped with Pthreads on multi-core node to make semi-sparse parallelization more easily. A shared zip file is read to cut down messages with Message Passing Interface package. The performance of proposed semi-sparse with multi-layer framework achieved a brilliant speedup in the evaluation of Netflix, MovieLens and MovieLen1600.
---
paper_title: Distributed scalable collaborative filtering algorithm

paper_content:

Collaborative filtering (CF) based recommender systems have gained wide popularity in Internet companies like Amazon, Netflix, Google News, and others. These systems make automatic predictions about the interests of a user by inferring from information about like-minded users. Real-time CF on highly sparse massive datasets, while achieving a high prediction accuracy, is a computationally challenging problem. In this paper, we present a novel design for soft real-time (less than 10 sec.) distributed co-clustering based Collaborative Filtering algorithm. Our distributed algorithm has been optimized for multi-core cluster architectures using pipelined parallelism, computation communication overlap and communication optimizations. Theoretical parallel time complexity analysis of our algorithm proves the efficacy of our approach. Using the Netflix dataset (100M ratings), we demonstrate the performance and scalability of our algorithm on 1024-node Blue Gene/P system. Our distributed algorithm (implemented using OpenMP with MPI) delivered training time of around 6s on the full Netflix dataset and prediction time of 2.5s on 1.4M ratings (1.78µs per rating prediction). Our training time is around 20× (more than one order of magnitude) better than the best known parallel training time, along with high accuracy (0.87±0.02 RMSE). To the best of our knowledge, this is the best known parallel performance for collaborative filtering on Netflix data at such high accuracy and also the first such implementation on multi-core cluster architectures such as Blue Gene/P.
---
paper_title: Parallel Implementation of the Slope One Algorithm for Collaborative Filtering

paper_content:

Recommender systems are mechanisms that filter information and predict a user's preference to an item. Parallel implementations of recommender systems improve scalability issues and can be applied to internet-based companies having considerable impact on their profits. This paper implements two parallel versions of the collaborative filtering algorithm Slope One, which has advantages such as its efficiency and the ability to update data dynamically. The first presented version is parallely implemented with the use of the OpenMP API and its performance is evaluated on a multi-core system. The second is an hybrid approach using both OpenMP and MPI and its performance is evaluated in an homogeneous and an heterogeneous cluster. Experiments proved that the multithreaded version is 9,5 times faster than the sequential algorithm.
---

Title: Parallel and Distributed Collaborative Filtering: A Survey

Section 1: INTRODUCTION
Description 1: This section introduces the necessity and benefits of parallel and distributed collaborative filtering systems in the context of recommender systems.

Section 2: Parallel and Distributed Computing
Description 2: This section explores parallel and distributed computing techniques and how they are applied in recommender systems.

Section 3: Evaluation Metrics
Description 3: This section details the various metrics used to evaluate the performance of recommender systems and their importance.

Section 4: Datasets
Description 4: This section highlights the datasets commonly used in recommender system research and their characteristics.

Section 5: Classification Scheme
Description 5: This section provides an overview of the structure and classification of existing studies in parallel and distributed collaborative filtering.

Section 6: RELATED WORK
Description 6: This section categorizes and summarizes previous surveys on recommender systems, noting areas they cover and those they omit.

Section 7: DISTRIBUTED IMPLEMENTATIONS
Description 7: This section discusses various distributed implementations of collaborative filtering algorithms, categorized by type and year.

Section 8: Distributed Memory-Based Collaborative Filtering
Description 8: This section details distributed memory-based collaborative filtering implementations, focusing on different algorithmic strategies.

Section 9: Distributed Model-Based Collaborative Filtering
Description 9: This section provides an overview of distributed model-based collaborative filtering implementations and their evolution.

Section 10: Hybrid Distributed Collaborative Filtering Methods
Description 10: This section covers hybrid approaches that combine model-based and memory-based methods in distributed collaborative filtering.

Section 11: Distributed Memory Implementations
Description 11: This section presents implementations on distributed memory systems, focusing on how specific algorithms are parallelized.

Section 12: Shared Memory Implementations
Description 12: This section describes collaborative filtering algorithms implemented on shared memory architectures, detailing their design and performance.

Section 13: GPU-Based Implementations
Description 13: This section explores the use of GPUs in parallelizing collaborative filtering algorithms, detailing the methods and their performance.

Section 14: PLATFORM-BASED RECOMMENDATIONS
Description 14: This section discusses implementations using large-scale data processing platforms like Hadoop and Spark, focusing on both memory-based and model-based methods.

Section 15: HETEROGENEOUS IMPLEMENTATIONS
Description 15: This section describes the hybrid implementations that employ both distributed and shared memory parallelization techniques.

Section 16: DISCUSSION AND CONCLUSIONS
Description 16: This section provides insights and summarizes the findings of the survey, discussing current trends, challenges, and future directions in the field.