Sun, 27 Jul 2008 07:32:09 BST CiteULike: pdlug's google http://www.citeulike.org/user/pdlug/tag/google CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/pdlug/article/2152671 <i>Science of Computer Programming, Vol. 70, No. 1. (1 January 2008), pp. 1-30.</i><br /><br />Google's MapReduce programming model serves for processing large data sets in a massively parallel manner. We deliver the first rigorous description of the model including its advancement as Google's domain-specific language Sawzall. To this end, we reverse-engineer the seminal papers on MapReduce and Sawzall, and we capture our findings as an executable specification. We also identify and resolve some obscurities in the informal presentation given in the seminal papers. We use typed functional programming (specifically Haskell) as a tool for design recovery and executable specification. Our development comprises three components: (i) the basic program skeleton that underlies MapReduce computations; (ii) the opportunities for parallelism in executing MapReduce computations; (iii) the fundamental characteristics of Sawzall's aggregators as an advancement of the MapReduce approach. Our development does not formalize the more implementational aspects of an actual, distributed execution of MapReduce computations. Google's MapReduce programming model -- Revisited Ralf Lammel doi:10.1016/j.scico.2007.07.001 Science of Computer Programming, Vol. 70, No. 1. (1 January 2008), pp. 1-30. 2007-12-20T18:37:33-00:00 2008 Science of Computer Programming 70 1 1 30 distributed google language languages mapreduce parallel programming http://www.citeulike.org/user/pdlug/article/2719467 <i>(8 May 2007)</i><br /><br />Several approaches to collaborative filtering have been studied but seldom have the studies been reported for large (several millions of users 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 adaptible 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. Google News Personalization: Scalable Online Collaborative Filtering Abhinandan Das Mayur Datar Ashutosh Garg Shyam Rajaram (8 May 2007) 2008-04-25T21:00:08-00:00 2007 collaborative-filtering filtering google machine-learning mapreduce recommendation http://www.citeulike.org/user/pdlug/article/936194 <i>OSDI '06, pp. 205-218.</i><br /><br />Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size: petabytes of data across thousands of commodity servers. Many projects at Google store data in Bigtable, including web indexing, Google Earth, and Google Finance. These applications place very different demands on Bigtable, both in terms of data size (from URLs to web pages to satellite imagery) and latency requirements (from backend bulk processing to real-time data serving). Despite these varied demands, Bigtable has successfully provided a flexible, high-performance solution for all of these Google products. In this paper we describe the simple data model provided by Bigtable, which gives clients dynamic control over data layout and format, and we describe the design and implementation of Bigtable. <!-- CHANGE -->Bigtable: A Distributed Storage System for Structured Data OSDI '06, pp. 205-218. 2006-11-08T12:02:38-00:00 OSDI '06 205 218 data database db distributed google http://www.citeulike.org/user/pdlug/article/983570 <i>(21 Nov 2004)</i><br /><br />Are we smarter now than Socrates was in his time? Society as a whole certainly enjoys a higher degree of education, but humans as a species probably don't get intrinsically smarter with time. Our knowledge base, however, continues to grow at an unprecedented rate, so how then do we keep up? The printing press was one of the earliest technological advances that expanded our memory and made possible our present intellectual capacity. We are now faced with a new technological advance of the same magnitude--the internet--but how do we use it effectively? A new tool is available on Google (<a href="http://www.google.com">this http URL</a>) that allows a user not only to numerically evaluate equations, but to automatically perform unit analysis and conversion as well, with most of the fundamental physical constants built in. Physics the google way David Ward (21 Nov 2004) 2006-12-07T16:58:47-00:00 2004 education fun google phsics search web http://www.citeulike.org/user/pdlug/article/430834 <i>OSDI '04, pp. 137-150.</i><br /><br />MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a _map_ function that processes a key/value pair to generate a set of intermediate key/value pairs, and a _reduce_ function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. <P> Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter- machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. <P> Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day. <P> MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean Sanjay Ghemawat OSDI '04, pp. 137-150. 2005-12-08T17:08:27-00:00 OSDI '04 137 150 algorithm algorithms cmpsci cs distributed google mapreduce http://www.citeulike.org/user/pdlug/article/591891 <i>(18 Apr 2006)</i><br /><br />We apply the Google PageRank algorithm to assess the relative importance of all publications in the Physical Review family of journals from 1893--2003. While the Google number and the number of citations for each publication are positively correlated, outliers from this linear relation identify some exceptional papers or "gems" that are universally familiar to physicists. Finding Scientific Gems with Google P Chen H Xie S Maslov S Redner (18 Apr 2006) 2006-04-20T13:17:44-00:00 2006 academic citation citations google informationretrieval ir pagerank search http://www.citeulike.org/user/pdlug/article/409469 <i>(1 Nov 2005)</i><br /><br />Search engines have become key media for our scientific, economic, and social activities by enabling people to access information on the Web in spite of its size and complexity. On the down side, search engines bias the traffic of users according to their page-ranking strategies, and some have argued that they create a vicious cycle that amplifies the dominance of established and already popular sites. We show that, contrary to these prior claims and our own intuition, the use of search engines actually has an egalitarian effect. We reconcile theoretical arguments with empirical evidence showing that the combination of retrieval by search engines and search behavior by users mitigates the attraction of popular pages, directing more traffic toward less popular sites, even in comparison to what would be expected from users randomly surfing the Web. The egalitarian effect of search engines Santo Fortunato Alessandro Flammini Filippo Menczer Alessandro Vespignani (1 Nov 2005) 2005-11-27T04:40:53-00:00 2005 academic google network networks paper search social http://www.citeulike.org/user/pdlug/article/416473 <i>Nature, Vol. 438, No. 7068. (30 November 2005), pp. 554-555.</i> Science in the web ageStart your engines Jim Giles doi:10.1038/438554a Nature, Vol. 438, No. 7068. (30 November 2005), pp. 554-555. 2005-11-30T19:43:01-00:00 2005 Nature 0028-0836 438 7068 554 555 Nature Publishing Group academic google nature publishing search http://www.citeulike.org/user/pdlug/article/90472 <i>OSDI (2004)</i> MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean Sanjay Ghemawat OSDI (2004) 2005-02-09T03:00:03-00:00 2004 OSDI distributed distributedcomputing google http://www.citeulike.org/user/pdlug/article/251211 <i>(October 2003)</i> The Google File System Sanjay Ghemawat Howard Gobioff Shun-Tak Leung (October 2003) 2005-07-10T05:32:09-00:00 2003 distributed filesystem google http://www.citeulike.org/user/pdlug/article/227597 <i>Scientific Programming Journal</i><br /><br />Very large data sets often have a flat but regular structure and span multiple disks and machines. Examples include telephone call records, network logs, and web document repositories. These large data sets are not amenable to study using traditional database techniques, if only because they can be too large to fit in a single relational database. On the other hand, many of the analyses done on them can be expressed using simple, easily distributed computations: filtering, aggregation, extraction of statistics, and so on. We present a system for automating such analyses. A filtering phase, in which a query is expressed using a new programming language, emits data to an aggregation phase. Both phases are distributed over hundreds or even thousands of computers. The results are then collated and saved to a file. The design -- including the separation into two phases, the form of the programming language, and the properties of the aggregators -- exploits the parallelism inherent in having data and computation distributed across many machines. Interpreting the Data: Parallel Analysis with Sawzall (Draft) Rob Pike Sean Dorward Robert Griesemer Sean Quinlan Scientific Programming Journal 2005-06-14T12:59:31-00:00 Scientific Programming Journal distributed google grid language mapreduce