Large-scale graph computing at Google

Posted by Grzegorz Czajkowski, Systems Infrastructure Team

If you squint the right way, you will notice that graphs are everywhere. For example, social networks, popularized by Web 2.0, are graphs that describe relationships among people. Transportation routes create a graph of physical connections among geographical locations. Paths of disease outbreaks form a graph, as do games among soccer teams, computer network topologies, and citations among scientific papers. Perhaps the most pervasive graph is the web itself, where documents are vertices and links are edges. Mining the web has become an important branch of information technology, and at least one major Internet company has been founded upon this graph.

Despite differences in structure and origin, many graphs out there have two things in common: each of them keeps growing in size, and there is a seemingly endless number of facts and details people would like to know about each one. Take, for example, geographic locations. A relatively simple analysis of a standard map (a graph!) can provide the shortest route between two cities. But progressively more sophisticated analysis could be applied to richer information such as speed limits, expected traffic jams, roadworks and even weather conditions. In addition to the shortest route, measured as sheer distance, you could learn about the most scenic route, or the most fuel-efficient one, or the one which has the most rest areas. All these options, and more, can all be extracted from the graph and made useful — provided you have the right tools and inputs. The web graph is similar. The web contains billions of documents, and that number increases daily. To help you find what you need from that vast amount of information, Google extracts more than 200 signals from the web graph, ranging from the language of a webpage to the number and quality of other pages pointing to it.

In order to achieve that, we have created scalable infrastructure, named Pregel, to mine a wide range of graphs. In Pregel, programs are expressed as a sequence of iterations. In each iteration, a vertex can, independently of other vertices, receive messages sent to it in the previous iteration, send messages to other vertices, modify its own and its outgoing edges' states, and mutate the graph's topology (experts in parallel processing will recognize that the Bulk Synchronous Parallel Model inspired Pregel).

Currently, Pregel scales to billions of vertices and edges, but this limit will keep expanding. Pregel's applicability is harder to quantify, but so far we haven't come across a type of graph or a practical graph computing problem which is not solvable with Pregel. It computes over large graphs much faster than alternatives, and the application programming interface is easy to use. Implementing PageRank, for example, takes only about 15 lines of code. Developers of dozens of Pregel applications within Google have found that "thinking like a vertex," which is the essence of programming in Pregel, is intuitive.

We've been using Pregel internally for a while now, but we are beginning to share information about it outside of Google. Greg Malewicz will be speaking at the joint industrial track between ACM PODC and ACM SPAA this August on the very subject. In case you aren't able to join us there, here's a spoiler: The seven bridges of Königsberg — inspiration for Leonhard Euler's famous theorem that established the basics of graph theory — spanned the Pregel river.

Google Fusion Tables

Posted by Alon Halevy, Google Research and Rebecca Shapley, User Experience

Database systems are notorious for being hard to use. It is even more difficult to integrate data from multiple sources and collaborate on large data sets with people outside your organization. Without an easy way to offer all the collaborators access to the same server, data sets get copied, emailed and ftp'd--resulting in multiple versions that get out of sync very quickly.


Today we're introducing Google Fusion Tables on Labs, an experimental system for data management in the cloud. It draws on the expertise of folks within Google Research who have been studying collaboration, data integration, and user requirements from a variety of domains. Fusion Tables is not a traditional database system focusing on complicated SQL queries and transaction processing. Instead, the focus is on fusing data management and collaboration: merging multiple data sources, discussion of the data, querying, visualization, and Web publishing. We plan to iteratively add new features to the systems as we get feedback from users.


In the version we're launching today, you can upload tabular data sets (right now, we're supporting up to 100 MB per data set, 250 MB of data per user) and share them with your collaborators or with the world. You can choose to share all of your data with your collaborators, or keep parts of it hidden. You can even share different portions of your data with different collaborators.


When you edit the data in place, your collaborators always get the latest version. The attribution feature means your data will get credit for its contribution to any data set built with it. And yes, you can export your data back out of the cloud as CSV files.


Want to understand your data better? You can filter and aggregate the data, and you can visualize it on Google Maps or with other visualizations from the Google Visualization API. In this example, an intensity map of the world shows countries that won more than 10 gold medals in the Summer Olympics. You can then embed these visualizations in other properties on the Web (e.g., blogs and discussion groups) by simply pasting some HTML code we provide you.


The power of data is truly harnessed when you combine data from multiple sources. For example, consider combining data about access to fresh water in various countries with data about malaria rates in those countries, or as shown here, showing three sources of GDP data side by side. Fusion Tables enables you to fuse multiple sets of data when they are about the same entities. In database speak, we call this a join on a primary key but the data originates from multiple independent sources. This is just the start, more join capabilities will come soon.


But Fusion Tables doesn't require you and your collaborators to stop there. What if you don't agree on all of the values? Or need to understand the assumptions behind the data better? Fusion Tables enables you to discuss data at different granularity levels -- you can discuss individual rows or columns or even individual cells. If a collaborator with edit permission changes data during the discussion, viewers will see the change as part of the discussion trail.


We hope you find Fusion Tables useful. As usual with first releases, we realize there is much missing, and we look forward to hearing your feedback.

Remembering Rajeev Motwani

Posted by Alfred Spector, VP of Research

Many hundreds of us at Google were fortunate to have been educated, advised, and inspired by Professor Rajeev Motwani. Six of us were his PhD students and very many others (including our founders) were advised by or took courses from him. Others Googlers, who were not students at Stanford, had close collegial relations. But, no matter what the relationship, we respected Rajeev as a great man. He was not just a mathematically deep computer scientist, not just an entrepreneurial computer scientist who catalyzed value at the intersection of his work and the real world, he was also a thoughtful, caring, and honorable friend.

The words of just a few of us speak louder than any summary I can make:

Sergey Brin wrote in his blog, “Officially, Rajeev was not my advisor, and yet he played just as big a role in my research, education, and professional development. In addition to being a brilliant computer scientist, Rajeev was a very kind and amicable person and his door was always open. No matter what was going on with my life or work, I could always stop by his office for an interesting conversation and a friendly smile.”

Zoltan Gyongyi wrote, “Not only a great educator and one of the brightest researchers of his generation, Rajeev was also a catalyst of Silicon Valley innovation--Google itself standing as a proof. Moreover, he was a mentor, colleague, role model, friend to many Googlers. I am utterly unable to find words that would properly express my personal gratitude to him and the weight of this loss.”

Mayur Datar wrote, “I was fortunate to have Rajeev as my PhD advisor for five years at Stanford. Beyond graduation, he often helped me with priceless career guidance and professional help in terms of meetings with other people in Silicon Valley. There are only a handful of people I can think of who are such high caliber academics and entrepreneurs. His contributions and impact on CS theory community, Stanford CS Dept, and Silicon Valley enterprises and entrepreneurs is unfathomable. I still find it hard to come to terms with his horrible reality. My deepest condolences and prayers go out to his family. He will be fondly remembered and dearly missed by all of us!"

An Zhu wrote, “I am both fortunate and honored to have Rajeev as my PhD advisor. The 5 years at Stanford is very memorable to me. I’m eternally grateful for his advice and support throughout. It is indeed a sad day for many, including his students.”

Alon Halevy wrote, “Rajeev was an inspiration to me and my colleagues on so many levels. As a young graduate student, I remember him working on some of the toughest theoretical computer science problems of the day. Later, his taste for good theory and ability to apply it to practice had a huge impact on various aspects of data management research. As a professor, and now as a Googler, I am awed at the amazing stream of high-caliber students that he mentored. As an entrepreneur, he gave me some generous and well-timed advice. And most of all, as a person, his kindness and willingness to help anyone was a true inspiration.”

Vibhu Mittal wrote, “He was a brilliant researcher and a great professor. And yet the only thing that I can remember right now is that he was a fun, generous, helpful guy who was always willing to sit down and chat for a few minutes. I hope wherever he is, he is still doing it. And I hope there’ll be more people like him in this world to help people like us. I wish his family well — words cannot express what I feel for them.”

Gagan Aggarwal wrote, “I feel extremely fortunate to have had Rajeev as my PhD advisor. He was a wonderful advisor--always very flexible and willing to let his students work at their own pace, while making sure that things are going alright and providing guidance when needed. One of the several striking features of Rajeev's research was his ability to translate real life problems into clean, well-motivated, abstract questions (that he would promptly pose to his students). He was for me an eternal source of fresh problems and great ideas, a source I could tap into whenever my own ideas dried up (and was planning to, just last week). It is impossible to come to terms with the fact that I am never going to do this again. Rajeev had an unmatched clarity of thought and perceptiveness that was evident not only in doing research with him but also in the invaluable advice he gave me about career choices and life in general. ...Rajeev took on many diverse roles: teacher, entrepreneur, advisor and friend, and filled them all as only he could have. His passing will leave an impossible-to-fill void among all those whose lives he touched.”

There are more notes from Googlers, among those of many others, on the Stanford blog commemorating Rajeev.

I’d like to close by noting that Rajeev Motwani’s work on the intersection of theory and practice inspired not only the way Google processes information, but also Google's core scientific values: we fundamentally believe in the power of applying mathematical analysis and algorithmic thinking to challenging real world problems. This philosophy was inherent in Rajeev’s research, the education he gave PhD students, and the advice and classes he provided to many more.

With his and the recent untimely deaths of other influential computer scientists and friends, we are all reminded to seize each day and make the most of it. I think Rajeev would have wanted us to keep this in mind.

Google Fellowships, the Nuts and Bolts

Posted by Leslie Yeh Johnson, Google University Relations

As you may have read, today we announced the recipients of the 2009 Google Fellowships. (You can read the announcement over on the Official Google Blog.) This is fantastic news, and the blog post makes the Google Fellowship Program sound very polished. But the truth is there was a lot more work (and scrambling) done in the background...here's a quick snapshot.

We first conceived of the idea of the fellowships late last year. Google already funds academic research through the Google Research Awards, but we really wanted to support the graduate students who are doing a lot of the research and are the future of their respective fields. Idea: why don't we search out the best and brightest PhD students and pay their tuition and expenses, plus give them an Android phone and hook them up with a Google researcher so we can all share really cool ideas? Done and done.

After we made the decision to do the fellowships in 2009, we were in for some hard work. We quickly spread the word about the fellowships in order to give the universities and students time to prepare and send us information about themselves and their research. The nominated students were doing research on a vast array of subjects: Cloud Computing, Computer Graphics, Market Algorithms, Machine Learning, Natural Language Processing, Social Computing, Information Retrieval, Compilers, and Computer Vision to name a few. I relied upon a small army of research scientists and distinguished engineers to help me review them. In addition to lending their scientific expertise to looking over the Google Research Awards, not to mention their "day job", the forty-five Googlers also were able to provide feedback on the students in record time - these guys are champs. Then a whirlwind review with Alfred Spector, VP of Research and Special Initiatives at Google, and just six months later we are proud to announce the 2009 Google Fellowship recipients.

It was a jam-packed 6 months, and I'm really proud of how the program turned out this year. That said, I'm already looking forward to our sophomore year in 2010. You should expect to see a broader program covering more areas of research, more schools, and more geographies. I can't wait.

The best and the brightest

Posted by Leslie Yeh Johnson, Google University Relations

[Also posted on the Official Google Blog]

I can't think of a better environment than academia for asking hard questions and trying to solve the unsolvable. It's at universities that graduate students perform some of the most exciting and game-changing research in computer science and technology. These university labs foster the students that are going to be the next innovators and leaders in research.

We started the Google Fellowship Program this year to support graduate students in their quest to discover and achieve great things. Our goal was to find the best and brightest PhD students and award them a unique fellowship that highlights their contributions to research and supports them through their graduate studies. Several top universities submitted their students for consideration by research scientists, distinguished engineers and executives at Google. The breadth of research covered by these students and the scope of their vision was astounding. Learning about them was exciting; choosing from among them was truly difficult.

After careful review, we are proud to announce the 2009 Google Fellowship recipients:

• Roxana Geambasu, Google Fellowship in Cloud Computing (University of Washington)
• Michael Piatek, Google Fellowship in Computer Networking (University of Washington)
• David Sontag, Google Fellowship in Machine Learning (Massachusetts Institute of Technology)
• Ali Farhadi, Google Fellowship in Computer Vision Image Interpretation (University of Illinois at Urbana-Champaign)
• Nicholas Chen, Google Fellowship in Human-Computer Interaction (University of Maryland)
• Siddhartha Sen, Google Fellowship in Fault Tolerant Computing (Princeton University)
• Ryan Peterson, Google Fellowship in Distributed Systems (Cornell University)
• Eric Gilbert, Google Fellowship in Social Computing (University of Illinois at Urbana-Champaign)
• Micha Elsner, Google Fellowship in Natural Language Processing (Brown University)
• Subhransu Maji, Google Fellowship in Computer Vision Object Recognition (University of California, Berkeley)
• Nicolas Lambert, Google Fellowship in Market Algorithms (Stanford University)
• Han Liu, Google Fellowship in Statistics (Carnegie Mellon University)
• Lixia Liu, Google Fellowship in Compiler Technology (Purdue University)

These students exemplify excellence in all areas, and we look forward to the impact that they are sure to have on their fields and the world. The Google Fellowship will provide them with funding to cover their tuition and expenses, plus an Android-powered phone and a Google mentor. Our sincere congratulations to all of them!

ACM Multimedia 2009 Grand Challenges

Posted by Jay Yagnik, Head of Computer Vision Research

At Google Research we interact with the academic research community closely through various programs like Research Awards, Visiting Faculty Program, and by active participation in various conferences. Dealing with large quantities of data gives us some unique challenges and perspectives on various problems. In many cases entirely new problem classes begin to emerge. These problems often have not received attention from a broad part of the research community. In an effort to bridge this gap for multimedia problems, we participated in setting Grand Challenges for this year's ACM Multimedia Conference. We proposed "Robust, As-Accurate-As-Human Genre Classification for Video" as a challenge.

The majority of research in video analysis today focuses on surveillance video. While this is critical for a lot of security applications, it is incomplete in describing challenges that come up when we tackle a video retrieval and discovery application like YouTube. Analysis work beyond surveillance is often limited to specific categories like News and Sports that have well defined structures that the solution methods can explicitly work with. Our challenge aims to encourage more work in the area of semantic understanding of a broad variety of videos. Genre classification is a problem thats representative of some of the challenges that stem from the sheer diversity that can exist across video categories. The challenge will encourage new methods to solve these problems, as well as attempts at standardizing datasets to represent this problem. With internet video gaining popularity in an astounding magnitude, we believe this challenge will steer the multimedia research community towards challenges posed by the magnitude and variety of this new problem area.

We are grateful to Mor Naaman (Rutgers University) and Tat-Seng Chua (National University of Singapore) for organizing this industry challenge track at ACM Multimedia and inviting us to be a part of it.

Details of our challenge can be found here.

The bar-bet phenomenon: increasing diversity in mobile searches

Posted by Maryam Kamvar, Melanie Kellar, Rajan Patel and Ya Xu, Google Research

Historically, research suggests that web search on mobile phones has been limited when compared to the diverse set of queries which comprise computer-based search. Researchers attribute the homogeneous mobile search behavior in part to the phone's form factor and browsing capabilities. However, our new logs-based study indicates that high-end phones, like the iPhone, are changing the landscape of mobile search. We found that search from these phones has evolved not only to mimic computer web search patterns, but to exceed the expectations set by conventional web search in some cases.

We see iPhone searches mimicking computer-based search behavior in terms of query length (~3 words per query for computer and iPhone queries, as opposed to 2.5 words per query for conventional mobile queries) and query classification (notably the percentage of Adult and Entertainment searches have decreased on the iPhone relative to conventional mobile phones). But what is most surprising to us is that frequent searchers on iPhone surpass frequent searchers on computers in terms of the diversity of queries they issue. In other words, people are using high-end phones to search for a more diverse set of information needs than computers are used for; we jokingly refer to this as the "bar-bet" phenomenon -- or the "pub-quiz" phenomenon for those of you in the UK.

We devised a metric for quantifying the variability of a user’s search intentions across time. This variability metric, entro-percent, is a normalized entropy metric which compares the number of search tasks issued by a user to the number of categories those search tasks fall under. This user-variability for conventional mobile web search is much lower than for computer-based search, confirming the hypothesis that mobile web users query over a much less diverse set of topics. The surprising news is that iPhone users, on the other hand, had a higher variability than computer based users, indicating their information needs are more diverse! This shows that the challenges posed by a phone's form factor can be outweighed by its "always on, always in your pocket" benefits.

To understand the meaning of the entro-percent equation, read our full paper summarizing the findings of our logs-based study of search patterns on conventional mobile phones, iPhones and conventional computers and get all the juicy details.