Google Research Blog

Google's Research Awards Program Update

2009-07-14T13:30:00.000-07:00

Posted by Posted by Juan E. Vargas, University Relations

When we think about innovation, it is easy to forget that it took about 55 years to spread automobile usage to 1/4 of the US population, ... 35 years for the telephone, ... 20 years for the radio, ... 15 years for the PC, ... 10 years for the cell phone, ... 7 years for the Internet (Council of Competiveness, Innovate America, 2004).

Recognizing that innovation holds the key to many of the unique technical challenges we face, we remain committed to maintaining strong relations with the academic research community. Our Research Awards Program has experienced phenomenal growth. Of the total number of applications that we received since the program's inception in 2005, more than half were submitted in the past year. To cope with the increased level of interest worldwide, we reorganized the program to accept submissions three times per year: April 15th, August 15th, and December 15th. Proposals are evaluated by teams of engineers and researchers, who make recommendations for funding. We try to move fast. Investigators receive a response about three months after their submission.

Here are some highlights from a recent round of applications:

"Recognition and Modeling of Objects from Street View Scans of Cities"
Thomas Funkhouser, Princeton University
Professor Funkhouser aims to develop methods for automatic construction of semantically-labeled, detailed, and photorealistic 3D models of cities from Street View data. The main efforts will be towards the segmentation and recognition of small objects (e.g. mailboxes, fire hydrants, parking meters, etc.) in Lidar data based on shape classification and contextual reasoning. A second objective will be to construct seamless, photorealistic 3D models of complete cities by extracting and fitting parts from repositories of polygonal models.

"An Ad Auctions Trading Agent Competition"
Michael Wellman, University of Michigan
The University of Michigan will introduce and operate a new game in the Trading Agent Competition (TAC) series of research competitions, in the domain of sponsored search. The TAC Ad Auctions (TAC/AA) game challenges participants to develop bidding strategies for advertisers in a simulated retail home entertainment market. The aim is to spur research and generate insights about advertiser bidding strategy, in a scenario more complex than those considered in the research literature to date. The TAC/AA environment features multiple interrelated keywords, a structured search user model, rich data availability, and a dynamic market context. Since 2000, the annual TAC series has catalyzed research on trading agent design and analysis, produced by a diverse group of researchers from academia and industry.

"A Suite of Automated Tools for Efficient Management and Search in Web-based Arabic Documents"
Adnan Yahya, Birzeit University, Palestine.
This research aims to design text mining and processing tools that are able to efficiently index, process, search, and categorize large quantities of Arabic data. This research addresses the challenges Arabic poses for NLP and information retrieval, automatic Arabic document categorization, root extraction, language detection, and Arabic query correction, suggestion and expansion. The PIs employ a statistical/Corpus-based approach based on contemporary data initially obtained from a local newspaper.

"When Children Search: Understanding what they do and what they could do with Google Search"
Allison Druin, University of Maryland
Children ages 5-13 are among the most frequent users of the Internet; yet, searching and browsing the web can present many challenges. Spelling, typing, query formulation, and deciphering results are all barriers for children in attempting to find the information they need. Professor Druin is trying to understand these issues in more diverse ages of children by focusing on current and ubiquitous search tools, namely, keyword-based web search engines.

"An Educational Camera for Kids"
Shree Nayar, Columbia University
Professor Nayar is desiging a novel digital camera that could be used as an innovative educational medium. His target audience is students between the ages of 10 and 13 years living in poor communities across the globe. The camera, named “Bigshot,” will be presented to students as a kit to expose them to diverse science and engineering concepts. Once assembled, the camera will be used so that students can share their photos with students in other cultures using Picasa and Google Groups.

"Discovering semantic concepts and their relations in large image collections"
Bernt Schiele, Technische Unversitat Darmstadt, Germany
Professor Schiele will investigate to what extent meaningful structures can be discovered from large sets of images both in a fully unsupervised fashion as well with minimal human supervision. To this end, Professor Schiele's work will try to first discover structure and learn multi-feature distance metrics in large collections of images and then to enrich such structure by weak annotations in order to link discovered structure and to derive semantic concepts.

"Dataspace Metrics: Measuring Progress for Pay-as-you-go Information Integration"
Michael Franklin, University of California
The goal of this project is to develop a measurement framework for gauging progress in terms of the quality and accuracy of information integration. The starting point is the development of a set of metrics for judging the “goodness’ of information integration across a number of information types and use cases. These metrics will then be analyzed and where possible, unified, so that a more general measurement framework can be developed. Such a framework will serve as a key component for future Dataspace management systems, and could provide a grounding for other collaborative information integration solutions.

For more information about this program, including submission guidelines, please visit the Research Awards Program page.

International Conference on Machine Learning (ICML 2009) in Montreal

2009-07-02T16:00:00.000-07:00

Posted by Eyal Even Dar and Vahab Mirrokni, Google Research, NY

The 26th International Conference on Machine Learning (ICML 2009) was recently held in Montreal in conjunction with the 22nd Conference On Learning Theory (COLT 2009) and the 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009). This is one of the major forums for researchers from both industry and academia to share the recent developments in the area of machine learning and artificial intelligence. Machine learning is a central area for Google as it has many applications in extracting useful information from a vast amount of data available on the web. In addition to sponsoring this scientific event, Google contributed intellectually to several scientific forums. Here's a short report of those activities:

There were ten papers co-authored by Googlers in these conferences, which covered several areas of machine learning including domain adaption, online learning, bandits, boosting, sparsity and kernel learning.
Corinna Cortes, the head of Google Research NY gave one of the three invited talks of ICML. She surveyed the last decade of research in learning kernels and highlighted both the successes and the failures in learning kernels with a focus on applications of convex optimization for this purpose. Corinna concluded with a call for applying new ideas and novel techniques to overcome the current obstacles.
We presented a tutorial on Convergence of Natural Game Dynamics. This topic has received a lot of attention recently as it stands at the conflux of many fields such as economics, machine learning and theoretical computer science. In the tutorial, we surveyed the convergence properties of the most natural game dynamics such as the Nash dynamics or the best-response dynamics to the popular no-regret learning-based dynamics. The tutorial highlighted similarities and differences between the approaches in both the time of convergence, the point of convergence, and the quality of the outcome. We believe that the influence of the learning algorithms on the behavior of the users is an exciting and intriguing topic of research for many, and in particular for the analysis of ad auctions.

Google's main mission is "to organize the world's information and make it universally accessible and useful," and machine learning plays a fundamental role in both of these aspects. As a result, Google has invested significant resources in this area of research, and we look forward to continued participation and collaboration at these conferences for many more years.

Speed Matters

2009-06-23T15:15:00.000-07:00

Posted by Jake Brutlag, Web Search Infrastructure

At Google, we've gathered hard data to reinforce our intuition that "speed matters" on the Internet. Google runs experiments on the search results page to understand and improve the search experience. Recently, we conducted some experiments to determine how users react when web search takes longer. We've always viewed speed as a competitive advantage, so this research is important to understand the trade-off between speed and other features we might introduce. We wanted to share this information with the public because we hope it will give others greater insight into how important speed can be.

Speed as perceived by the end user is driven by multiple factors, including how fast results are returned and how long it takes a browser to display the content. Our experiments injected server-side delay to model one of these factors: extending the processing time before and during the time that the results are transmitted to the browser. In other words, we purposefully slowed the delivery of search results to our users to see how they might respond.

All other things being equal, more usage, as measured by number of searches, reflects more satisfied users. Our experiments demonstrate that slowing down the search results page by 100 to 400 milliseconds has a measurable impact on the number of searches per user of -0.2% to -0.6% (averaged over four or six weeks depending on the experiment). That's 0.2% to 0.6% fewer searches for changes under half a second!

Furthermore, users do fewer and fewer searches the longer they are exposed to the experiment. Users exposed to a 200 ms delay since the beginning of the experiment did 0.22% fewer searches during the first three weeks, but 0.36% fewer searches during the second three weeks. Similarly, users exposed to a 400 ms delay since the beginning of the experiment did 0.44% fewer searches during the first three weeks, but 0.76% fewer searches during the second three weeks. Even if the page returns to the faster state, users who saw the longer delay take time to return to their previous usage level. Users exposed to the 400 ms delay for six weeks did 0.21% fewer searches on average during the five week period after we stopped injecting the delay.

While these numbers may seem small, a daily impact of 0.5% is of real consequence at the scale of Google web search, or indeed at the scale of most Internet sites. Because the cost of slower performance increases over time and persists, we encourage site designers to think twice about adding a feature that hurts performance if the benefit of the feature is unproven. To learn more on how to improve the performance of your website visit code.google.com/speed. For more details on our experiments, download this PDF.

A new landmark in computer vision

2009-06-22T07:30:00.000-07:00

Posted by Jay Yagnik, Head of Computer Vision Research

[Cross-posted with the Official Google Blog]

Science fiction books and movies have long imagined that computers will someday be able to see and interpret the world. At Google, we think computer vision has tremendous potential benefits for consumers, which is why we're dedicated to research in this area. And today, a Google team is presenting a paper on landmark recognition (think: Statue of Liberty, Eiffel Tower) at the Computer Vision and Pattern Recognition (CVPR) conference in Miami, Florida. In the paper, we present a new technology that enables computers to quickly and efficiently identify images of more than 50,000 landmarks from all over the world with 80% accuracy.

To be clear up front, this is a research paper, not a new Google product, but we still think it's cool. For our demonstration, we begin with an unnamed, untagged picture of a landmark, enter its web address into the recognition engine, and poof — the computer identifies and names it: "Recognized Landmark: Acropolis, Athens, Greece." Thanks computer.

How did we do it? It wasn't easy. For starters, where do you find a good list of thousands of landmarks? Even if you have that list, where do you get the pictures to develop visual representations of the locations? And how do you pull that source material together in a coherent model that actually works, is fast, and can process an enormous corpus of data? Think about all the different photographs of the Golden Gate Bridge you've seen — the different perspectives, lighting conditions, and image qualities. Recognizing a landmark can be difficult for a human, let alone a computer.

Our research builds on the vast number of images on the web, the ability to search those images, and advances in object recognition and clustering techniques. First, we generated a list of landmarks relying on two sources: 40 million GPS-tagged photos (from Picasa and Panoramio) and online tour guide webpages. Next, we found candidate images for each landmark using these sources and Google Image Search, which we then "pruned" using efficient image matching and unsupervised clustering techniques. Finally, we developed a highly efficient indexing system for fast image recognition. The following image provides a visual representation of the resulting clustered recognition model:

In the above image, related views of the Acropolis are "clustered" together, allowing for a more efficient image matching system.

While we've gone a long way towards unlocking the information stored in text on the web, there's still much work to be done unlocking the information stored in pixels. This research demonstrates the feasibility of efficient computer vision techniques based on large, noisy datasets. We expect the insights we've gained will lay a useful foundation for future research in computer vision.

If you're interested to learn more about this research, check out the paper.

Large-scale graph computing at Google

2009-06-15T11:47:00.000-07:00

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

2009-06-09T16:00:00.000-07:00

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

2009-06-08T08:06:00.000-07:00

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.

The best and the brightest

2009-05-15T09:00:00.001-07:00

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!

Google Fellowships, the Nuts and Bolts

2009-05-15T09:00:00.000-07:00

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.

ACM Multimedia 2009 Grand Challenges

2009-05-12T07:19:00.000-07:00

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

2009-05-07T11:27:00.001-07:00

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.

Cloud Computing and the Internet

2009-04-28T08:17:00.000-07:00

Posted by Vinton Cerf, Chief Internet Evangelist

[adapted from the speech given on the occasion of the honoris causa ceremony
at the Universidad Politecnico de Madrid]

The Internet is largely a software artifact and a layered one as my distinguished colleague, Sir Tim Berners-Lee has observed on many occasions. The layering has permitted a remarkable versatility in the implementation of the Internet and its applications. New technology can be used to implement each layer and as long as the interfaces between the layers remain static, the changes do not affect the functionality of the system. In this way, the Internet has evolved and adapted new transmission and switching technology into its lower layers and has supported new upper layers such as the HTTP, HTML and SSL protocols of the World Wide Web.

In recent years, the term “cloud computing” has emerged to make reference to the idea that from the standpoint of a device, say a laptop, on the Internet, many of the applications appear to be operating somewhere in the network “cloud.” Google, Amazon, Microsoft and others, as well as enterprise operators, are constructing these cloud computing centers. Generally, each cloud knows only about itself and is unaware of the existence of other cloud computing facilities. In some ways, cloud computing is like the networks of the 1960s when my colleagues and I began to think about connecting computers together on networks. Each network was typically proprietary. IBM had Systems Network Architecture; Digital Equipment Corporation had its DECNET; Hewlett-Packard had its Distributed System. These networks were specific to each manufacturer and did not interconnect nor even have a way to express the idea of connecting to another network. The Internet was the solution that Robert Kahn and I developed to allow all such networks to be interconnected in a uniform way.

Cloud computing is at the same stage. Each cloud is a system unto itself. There is no way to express the idea of exchanging information between distinct computing clouds because there is no way to express the idea of “another cloud.” Nor is there any way to describe the information that is to be exchanged. Moreover, if the information contained in one computing cloud is protected from access by any but authorized users, there is no way to express how that protection is provided and how information about it should be propagated to another cloud when the data is transferred.

Interestingly, my colleague, Sir Tim Berners-Lee, has been pursuing ideas that may inform the so-called “inter-cloud” problem. His idea of data linking may prove to be a part of the vocabulary needed to interconnect computing clouds. The semantics of data and of the actions one can take on the data, and the vocabulary in which these actions are expressed appear to me to constitute the beginning of an inter-cloud computing language. This seems to me to be an extremely open field in which creative minds everywhere can be free to contribute ideas and to experiment with new concepts. It is a new layer in the Internet architecture and, like the many layers that have been invented before, it is an open opportunity to add functionality to an increasingly global network.

There are many unanswered questions that can be posed about this new problem. How should one reference another cloud system? What functions can one ask another cloud system to perform? How can one move data from one cloud to another? Can one request that two or more cloud systems carry out a series of transactions? If a laptop is interacting with multiple clouds, does the laptop become a sort of “cloudlet”? Could the laptop become an unintended channel of information exchange between two clouds? If we implement an inter-cloud system of computing, what abuses may arise? How will information be protected within a cloud and when transferred between clouds. How will we refer to the identity of authorized users of cloud systems? What strong authentication methods will be adequate to implement data access controls?

Because the Internet is primarily a software artifact, there seems to be no end to its possibilities. It is an endless frontier, open to exploration by virtually anyone. I cannot guess what will be discovered in these explorations but I am sure that we will continue to be surprised by the richness of the Internet’s undiscovered territory in the decades ahead.

The Continuing Metamorphosis of the Web

2009-04-27T10:39:00.000-07:00

Posted by Alfred Spector, VP Research and Special Initiatives

I just returned from giving a talk at the 18th World Wide Web Conference in Madrid and was pleased to see a healthy and dynamic conference despite difficult economic conditions. Madrid had beautiful spring weather, and a magnificent modern architecture abounds throughout the city. I will say, though, that the Madrid subway does not vibrate (shake, rattle, and roll) one’s soul quite as much as does our local NYC subway.

My talk was entitled The Continuing Metamorphosis of the Web. In it, I noted that the initial web standards were so simple and sensible that they engendered a path of stepwise innovations, which taken together have aggregated into amazing accomplishments. Metaphorically, I feel our community has been on a kind of pseudo-random walk that has taken us to remarkable places. The truly great results have included the creation of a virtual Library of Alexandria, the creation of the search engine (to be that library’s super-card catalog), the empowerment of the long tail (in diverse communities), and great innovations to doing business. I argued that the bottom up evolution is continuing (perhaps even accelerating) today, and that the current stepwise improvements are still leading to broad innovations, which we will come to view as extraordinary as any that have occurred to-date.

Here are three great achievements currently a-brewing:

“Totally Transparent Processing.” By this, I argued that our use of the web (whether for search, communication, or information access) can increasingly occur in a fluid manner that is independent of the device we are using, independent of the human language we prefer, independent of the modality of the data, and independent of the corpus of information on which our interaction is based. In effect, processing can be transparent ∀d∈D, ∀l∈L, ∀m∈M, ∀c∈C. Our barriers to using information technology are fading away and becoming transparent.
“Ideal Distributed Computing.” While we have known the fundamentals of distributed computing for many decades, only today are we reaching a state where we can achieve a powerful and efficient balance of computation between all end-user devices and a vast collection of shared storage and computational resources. Cloud computing is today’s term d’arte, but I talked more generally about systems with the flexibility that computation and data can move across computers within a cluster, across clusters of computers and—of course—between clusters and all other (say, end user) devices. The result is the efficient, even awesome, capability to provide communication, computation and data to a vast collection of people and applications.
“Hybrid, Not Artificial, Intelligence.” Systems are regularly augmenting the capability of all of us in day-to-day life, and our collective use of those systems is, in turn, augmenting the capabilities of those systems in a beneficial virtuous circle. The virtuous circle is operating already in the search engine, voice recognition systems, recommendation systems, and more. There is every reason to think the effect will become ever more potent as computers are applied to more domains and and used by larger populations. The result may not be artificially intelligent machines that pass the Turing Test, but instead systems that will be ever more capable of helping us achieve our goals in life -- in a kind of partnership. For a related take on this, you might look at a Google Official Blog post, “The Intelligent Cloud,” which Franz Och and I posted last Fall.

More explanation and many examples, based on Google research and services, are available in the slides I used with my talk. A PDF file of those slides is available on the WWW2009 website under the papers and presentations link.

Congratulations to NSF CLuE Grant awardees

2009-04-23T12:03:00.000-07:00

Posted by Jeff Walz and Andrea Held

The first goal of the Academic Cluster Computing Initiative was to familiarize the academic community with the methods necessary to run very large datasets on massive distributed computer networks. By expanding that program to include research grants through the National Science Foundation's Cluster Exploratory (CLuE) program, we're also hoping to enable new and better approaches to data-intensive research across a range of disciplines.

Now that the NSF has announced the 2009 CLuE grants in addition to some previous Small Grant for Exploratory Research (SGER) grants, we're excited to congratulate the recipient researchers and wish them the best as they bring new projects online and continue to run existing SGER projects on the Google/IBM cluster.

The NSF selected projects based on their potential to advance computer science as well as to benefit society as a whole, and researchers at 14 institutions are tackling ambitious problems in everything from computer science to bioinformatics. The institutions receiving CLuE grants are Purdue, UC Santa Barbara, University of Washington, University of Massachussetts-Amherst, UC San Diego, University of Virginia, Yale, MIT, University of Wisconsin-Madison, Carnegie Mellon, University of Maryland- College Park, University of Utah and UC Irvine. Florida International University, Carnegie Mellon and University of Maryland will continue other projects with exiting SGER grants. These grantees will run their projects on a Google/IBM-provided cluster running an open source implementation of Google's MapReduce and File System.

We're excited to help foster new approaches to difficult, data-intensive problems across a range of fields, and we can't wait to see more students and researchers come up with creative applications for massive, highly distributed computing.

Socially Adjusted CAPTCHAs

2009-04-16T10:58:00.000-07:00

Posted by Rich Gossweiler, Maryam Kamvar, Shumeet Baluja

Unfortunately, there is a war going on between humans and 'bots. Software
'bots are attempting to generate massive numbers of computer accounts
which are then sold in bulk to spammers. Spammers use these accounts to
inundate emails and discussion boards. Meanwhile humans are trying to
simply create an account and don't want to spend a lot of time proving
that they are not a program.

Typically we use CAPTCHAs -- we present an image of some distorted text
and then ask the applicant to type in the letters. As image processing gets
more sophisticated, these letter sequences tend to get longer and more
distorted, sometimes to the point where humans fail too.

So we switched the game. We show an image, say an airplane, but it
is randomly rotated and we ask the applicant to rotate it to "up." This
is generally hard for computers but easy for people. Well, for the most
part.

Since computers are good at faces, skies, text, etc. we sift
through our database of images running state-of-the-art up detectors to
remove those images. But of the images that remain, some are too hard
for people to figure out. What is up for a plate or a piece of
abstract art?

So here is where it gets interesting. We show people several images, one
of which is a "candidate" and we see how people do. If everyone rotates
it the same way, it is a keeper. If there is a lot of variation, we
discard it. As extra credit it turns out that even if the original image were
taken at an angle, it does not matter, since people, in large numbers,
socially adjust the CAPTCHA.

Read the full paper here (posted with the permission of WWW'09).

The Grill: Google's Alfred Spector on the hot seat

2009-04-15T11:05:00.000-07:00

Posted by Ben Bayer, Google Research

Alfred Spector, Google's VP of Research, tells COMPUTERWORLD the ins and outs of Research at Google and where it's headed for the future. Read the complete interview here.

Predicting the Present with Google Trends

2009-04-02T14:10:00.000-07:00

Posted by Hal Varian, Chief Economist and Hyunyoung Choi, Decision Support Engineering Analyst

Can Google queries help predict economic activity?

The answer depends on what you mean by "predict." Google Trends and Google Insights for Search provide a real time report on query volume, while economic data is typically released several days after the close of the month. Given this time lag, it is not implausible that Google queries in a category like "Automotive/Vehicle Shopping" during the first few weeks of March may help predict what actual March automotive sales will be like when the official data is released halfway through April.

That famous economist Yogi Berra once said "It's tough to make predictions, especially about the future." This inspired our approach: let us lower the bar and just try to predict the present.

Our work to date is summarized in a paper called Predicting the Present with Google Trends. We find that Google Trends data can help improve forecasts of the current level of activity for a number of different economic time series, including automobile sales, home sales, retail sales, and travel behavior.

Even predicting the present is useful, since it may help identify "turning points" in economic time series. If people start doing significantly more searches for "Real Estate Agents" in a certain location, it is tempting to think that house sales might increase in that area in the near future.

Our paper outlines one approach to short-term economic prediction, but we expect that there are several other interesting ideas out there. So we suggest that forecasting wannabes download some Google Trends data and try to relate it to other economic time series. If you find an interesting pattern, post your findings on a website and send a link to econ-forecast@google.com. We'll report on the most interesting results in a later blog post.

It has been said that if you put a million monkeys in front of a million computers, you would eventually produce an accurate economic forecast. Let's see how well that theory works ...

The Unreasonable Effectiveness of Data

2009-03-25T17:02:00.000-07:00

Posted by Fernando Pereira, Google Research

Alon Halevy, Peter Norvig, and I argue that we should stop acting as if our goal is to author extremely elegant theories, and instead embrace complexity and make use of the best ally we have: the unreasonable effectiveness of data. See the full article here (IEEE Intelligent Systems, March/April 2009).

Google and WPP Marketing Research Awards: Improving industry understanding and practices in online marketing

2009-03-19T11:10:00.000-07:00

Posted by Jeff Walz, University Relations and Anne Bray, Head of Agency, WPP

Google and the WPP Group have teamed up to create a new research program with the goal of improving industry understanding of digital marketing. Eleven research awards have been given to universities through the Google and WPP Marketing Research Awards Program, announced by both companies in the fall of 2008. The academic studies will harness WPP client data to explore how online media influences consumer behavior, attitudes, and decision making. The research provides an opportunity for very innovative thinking in an area that is at the crossroads of marketing, computer science, economics, and various mathematical disciplines.

More than 120 entries were received by the deadline for proposals. The awards represent the first round of grants in the three-year program towards which WPP and Google will commit up to $4.6 million in an effort to support research around digital marketing. Hal Varian, Google's Chief Economist, participated on the decision committee.

The winning projects offer convincing designs for exploring how online and offline marketing influence consumer attitudes, decisions, and purchase behavior. As marketing continues to become more digital and more measurable, the results of these studies will also advance our understanding of how advertising investment should be allocated among media channels.

The researchers and affiliated academic institutions participating in this first round of awarded projects are:

• “Effect of Online Exposure on Offline Buying: How Online Exposure
Aids or Hurts Offline Buying by Increasing the Impact of Offline
Attributes”; Amitav Chakravarti, New York University, Stern School of
Business, Department of Marketing

• “The Interaction Between Digital Marketing Tactics and Sales
Performance Online and Offline”; Elie Ofek, Associate Professor
Marketing, Harvard Business School and Zsolt Katona, Associate
Professor of Marketing, UC Berkeley, Haas School of Business

• ”Are Brand Attitudes Contagious? Consumer Response to Organic
Search Trends”; Donna L. Hoffman, Professor, A. Gary Anderson
Graduate School of Management, University of California Riverside and
Thomas P. Novak, A. Gary Anderson Graduate School of Management,
University of California Riverside

• “Does internet advertising help established brands or niche ("long
tail") brands more? Catherine Tucker, Assistant Professor of
Marketing, MIT Sloan School of Marketing and Avi Goldfarb, Associate
Professor of Marketing, Joseph L. Rotman School of Management
University of Toronto

• “Marketing on the Map: Visual Search and Consumer Decision Making”;
Nicolas Lurie, Assistant Professor of Marketing, College of
Management, Georgia Institute of Technology, College of Management and
Sam Ransbotham, Assistant Professor of Information Systems, Carroll
School of Management, Boston College

• “Methods for multivariate metric analysis; identifying change
drivers”; Trevor J. Hastie, Professor, Department of Statistics,
Stanford University

• “Unpuzzling the Synergy of Display and Search Advertising: Insights
from Data Mining of Chinese Internet Users”; Hairong Li, Department of
Advertising, Public Relations, and Retailing, Michigan State
University and Shuguang Zhao, Media Survey Lab, Tsinghua University

• “Optimal Allocation of Offline and Online Media Budget”; Sunil
Gupta, Professor of Business Administration, Harvard Business School;
Anita Elberse, Associate Professor, Harvard Business School; and
Kenneth C. Wilbur, Assistant Professor of Marketing, Marshall School
of Business, University of Southern California

• “Targeting Ads to Match Individual Cognitive Styles: A Market
Test”; Glen Urban, Professor, MIT Sloan School of Management

• “How do consumers determine what is relevant? A psychometric and
neuroscientific study of online search and advertising effectiveness”;
Antoine Bechara, Professor of Psychology and Neuroscience, Department
of Psychology/Brain & Creativity Institute, University of Southern
California and Martin Reimann, Fellow, Department of Psychology/Brain
& Creativity, University of Southern California

• “A Comprehensive Model of the Effects of Brand-Generated and
Consumer-Generated Communications on Brand Perceptions, Sales and
Share”; Douglas Bowman and Manish Tripathi, Professors of Marketing,
Goizueta Business School, Emory University.

You can find more information about the Google and WPP Marketing Research Awards Program on the website.

And the award goes to...

2009-03-18T09:22:00.000-07:00

Posted by Fernando Pereira, Research Director

Corinna Cortes, Head of Google Research in New York, has just been awarded the ACM Paris Kanellakis Theory and Practice Award jointly with Vladimir Vapnik (Royal Holloway College and NEC Research). The award recognizes their invention in the early 1990s of the soft-margin support vector machine, which has become the supervised machine learning method of choice for applications ranging from image analysis to document classification to bioinformatics.

What is so important about this invention? In supervised machine learning, we create algorithms that can learn a rule to accurately classify new examples based on a set of training examples (e.g. spam or non-spam). There is no single attribute of an email message that tells us with certainty that it is spam. Instead, many attributes have to be considered, forming a vector of very high dimension. The same situation arises in many other machine practical learning tasks, including many that we work on at Google.

To learn accurate classifiers, we need to solve several big problems. First, the rule learned from the training data should be accurate on new test examples, even though it has not seen those examples. In other words, the rule must generalize well. Second, we must be able to find the optimal rule efficiently. Both of these problems are especially daunting for very high dimensional data. Third, the method for computing the rule should be able to accommodate errors in the training data, such as messages that are given conflicting labels by different people (my spam may be your ham).

Soft-margin support vector machines wrap these three problems together into an elegant mathematical package. The crucial insight is that classification problems of this kind can be expressed as finding in very high dimension (or even infinite dimension) the hyperplane that best separates the positive examples (ham) from the negative ones (spam).

Remarkably, the solution of this problem does not depend on the dimensionality of the data, it depends only on the pairwise similarities between the training examples determined by the agreement or disagreement between corresponding attributes. Furthermore, a hyperplane that separates the training data well can be shown to generalize well to unseen data with the same statistical properties.

Now, you might be asking how could this be done if the training data is inconsistently labeled. After all, you cannot have the same example on both sides of the separating hyperplane. That's where the soft margin idea comes in: the quadratic optimization program that finds the optimal separating hyperplane can be cleverly modified to "give up" on a fraction of the training examples that cannot be classified correctly.

With this crucial improvement, support vector machines became really practical, while the core ideas have had huge influence in the development of further learning algorithms for an ever wider range of tasks.

Congratulations to Corinna (and Vladimir) on the well-deserved award.

Beyond Web-2.0

2009-02-18T16:08:00.000-08:00

Posted by T.V Raman, Research Scientist

A little over a year ago, I gave a lightning talk at the W3C Technical Plenary in Boston where I looked forward to what came after Web-2.0. The key insight underlying that talk was that the Web was now mature enough for us to build Web technologies purely out of Web parts. Web-2.0 is a result of applying the Web to itself and is therefore better thought of as Web(Web()) or more concisely, Web².

Today, we can build new web artifacts out of existing ones by aggregation (web mashups) and by projection (filtered views), and publish the resulting artifacts on the web by assigning them a URL. This leads to the insight that this web that is to come potentially consists of the power-set of all web content. These ideas, and their logical consequences are detailed in article entitled Toward 2^W --- Beyond Web 2.0 in the February edition of the Communications Of The ACM. You can also find a slightly more extensive blog I posted here.

Market Algorithms and Optimization Meeting

2009-01-28T10:25:00.000-08:00

Posted by Vahab S. Mirrokni and Muthu Muthukrishnan

Google auctions ads, and enables a market with millions of advertisers and users. This market presents a unique opportunity to test and refine economic principles as applied to a very large number of interacting, self-interested parties with a myriad of objectives. Researchers in economics, computer science, operations research, marketing and business are increasingly involved in defining, understanding and influencing this market.

On January 7th, a group of computer science researchers from Google and various universities formed a workshop to discuss key research directions in this area, specifically "Market Algorithms and Optimization." Corinna Cortes (Head, Google Research, NY) and Alfred Spector (VP of Research, Google) gave short talks about research groups in Google, academic collaborations, and research awards. The morning session comprised talks by Google researchers including Noam Nisan, Jon Feldman, Vahab Mirrokni, Yishay Mansour, and Muthu Muthukrishnan. These talks explored the following topics and key issues:

Role of budgets. Identify suitable properties of mechanisms for repeated auctions in the presence of budgets. Truthfulness is impossible, and may not be the suitable property.
Advertisers' bidding strategies. While bidding equally on all keywords has certain desirable properties, identify other bidding strategies if advertisers want to maximize different utility functions and use rich bidding features.
Dynamics of ad games. Understand dynamics of sophisticated advertiser bidder strategies under various ad allocation rules. For proportional allocation rules, the dynamics of simple bidder strategies are described here.
Online Reservations. Design suitable mechanisms for selling ad inventory in the future rather than on the spot. Models and methods for what happens when reservations can not be honored are explored in WWW08, WINE08, and SODA09 papers.

The research presented in these talks can be found at the Google publications site. Some general research directions and open problems in ad auctions are here.

The post-lunch (sushi included of course) session comprised talks by researchers from academia. Bobby Kleinberg (Cornell) went first and took the audience far into projective geometry in an attempt to understand equilibria resulting from a sequence of selfish behavior of players using specific learning algorithms. Silvio Micali (MIT) described how difficult it was to model or propose mechanisms in presence of collusions, and then went on to show how to correctly design such mechanisms for combinatorial auctions. Kamesh Munagala (Duke Univ.) and Anna Karlin ( U. Wash) discussed algorithmic problems related to ad auctions, including how to run auctions in presence of advertisers with mixed utilities and tight remnant budgets. Other participants -- Richard Cole (NYU), Amos Fiat (Tel Aviv), Uri Feige (Weizmann), Michel Goemans (MIT), Anupam Gupta (CMU), Nicole Immorlica (Northwestern), Michael Rabin (Harvard), and Eva Tardos (Cornell) -- kept it lively with questions and discussions.

Part of what makes Google ad systems exciting is the challenges they pose and overcome, and yet others in the horizon. It is remarkable how some of the fundamental problems Google ad systems grapple with are also some of the hardest research problems in the community of Market Algorithms. Joint Google and Academia meetings like this help researchers begin to attack these problems, and may be a model for research collaborations in the future.

Google University Research Awards

2009-01-28T09:56:00.000-08:00

Posted by Juan Vargas, University Relations

For most people, the word "Google" evokes associations of Internet search, free apps, and advertising--a far cry from our roots in research and academia. Google, however, has not lost sight of that fundamental relationship. Many of our offices (or "campuses") are located near local universities, and we maintain a working environment many consider to be collegiate: informal, collaborative, and home to expert lectures not only about science and technology, but also about literature, the economy, world peace, green energy, fitness, etc.

But these aspects are only one component of our enduring partnership with academia. Given the unique technical challenges we face, from the beginning we've often recognized the need for a strong relationship with the research community. One of the key ways we interact with this community is through the Google Research Awards Program.

Started in 2005, the program seeks to identify and support leading-edge research in strategic areas of engineering and computer science. Professors from universities worldwide submit proposals three times per year that are evaluated by a team of Google engineers and scientists.

Like Google itself, the program is global in scope: in the most recent round of submissions, nearly a third came from outside of the United States. During that round, we received 149 proposals and we ultimately decided to fund about a third of the projects.

A challenging aspect of running an awards program is making the funding decisions. We want to ensure that every proposal is reviewed by the best experts in the field. Luckily, we're fortunate to have many people at Google with the right expertise who help us make those decisions.

As Alfred Spector, VP for Research, explains, "The winning proposals not only get financial support from Google, but also receive the extra benefit of being assigned a Google liaison who maintains a special relation with the professor during the life of the award, contributes to the research, and ensures that the outcomes are valuable to Google and academia." One example of this is the recent paper featured on the Google Research home page, by Phil Long and Rocco Servedio from Columbia University titled "Random Classification Noise Defeats All Convex Potential Boosters."

The following are some highlights from other recently-funded projects:

Social Networks Research Through CourseRank

Hector Garcia-Molina, Stanford University

Hector Garcia-Molina and his team at Stanford are pursuing research on social networks and web usability by using and expanding CourseRank, a course evaluation and recommendation system for the Stanford community. As of June 2008, CourseRank has over 6,700 users and over 134,000 course evaluations. In addition to providing a service for Stanford students, it provides useful data to learn about social networks. Dr. Garcia-Molina plans to use CourseRank to investigate problems such as spam, trust, recommendations with complex objects, and the nature of social interactions. You can see a video with student testimonials and a demo here.

Energy-Efficient Storage Architectures for Data Centers

Sudhanva Gurumurthi, Mircea Stan, University of Virginia

Drs. Gurumurthi and Stan from the University of Virgina have developed a new disk drive architecture called "Intra-Disk Parallelism" that they hope will reduce the energy consumption of data center storage systems by over 60% while providing high performance to applications. This architecture extends conventional disk drives by allowing it to handle multiple I/O requests in parallel and by provisioning additional hardware resources to enhance the parallel capabilities even further. Details of their research were published at the 2008 International Symposium on Computer Architecture (ISCA ). The conference paper has also been selected to appear in the IEEE Micro special issue on Top Picks from Computer Architecture Conferences.

Finding Better Spoken Dialog System Metrics

Maxine Eskenazi, Carnegie Mellon University

When the number of calls to spoken dialog systems mounts into the thousands, or millions, it is impossible to listen to every call. Prof. Eskenazi and her team at CMU are studying new metrics that could improve the performance of those systems. Dr. Eskenazi hopes this research will help illuminate how best to cope with advances in tuned speech recognition and new synthetic voices.

Interested in learning more about the Google University Relations and our Research Awards Program? Please visit our web site where scholars can learn more and submit proposals.

Smart Thumbnails on YouTube

2009-01-19T17:35:00.000-08:00

Posted by Tomáš Ižo (Software Engineer) and Jay Yagnik (Head of Computer Vision Research)

One of our favorite aspects of Google web search are the informative snippets that appear with each search result. The more relevant they are, the quicker we can find what we're looking for. As members of the computer vision team, we're pleased to say that we now apply a similar philosophy to choosing thumbnails for videos on YouTube. After all, the thumbnail is the first visual piece of information our users get when searching or browsing YouTube videos. As we recently announced in a post on the YouTube Blog, our previous system of choosing thumbnails from the 25, 50 and 75% marks in the video, which often led to arbitrary, uninformative or sometimes even misleading images, is now a thing of the past. When a new video comes to YouTube, we now analyze it with an algorithm whose aim is to pick a set of images that are visually representative of the content of the video. As with the ground-breaking video identification tools that we launched on YouTube last year, this system is another example of how looking inside the video can lead to a safer, more relevant experience for our users.

Launching a computer vision algorithm on YouTube comes with a unique set of challenges, many of which have to do with the incredible diversity of the content and the awe-inspiring rate at which it pours into our servers: each minute YouTube receives as much as 13 hours of video content in a wide variety of genres, styles, formats and resolutions. Of course, even with some of the technical challenges aside, our work is far from finished. We'll keep on studying how our users interact with thumbnails and, more generally, with video content on the web, and we'll continue thinking of innovative ways to use computer vision and machine learning to improve the experience.

Maybe your computer just needs a hug

2009-01-12T07:45:00.000-08:00

Posted by Anthony Francis

Maybe your computer just needs a hug
I'm Anthony Francis, an artificial intelligence researcher working in Google's Search Quality group. One of the things I like about Google is that we give back to the world in ways that make sense for our business, both as a company and as individuals. Google's search engine runs on electrical power, and so Google as a company invests in renewable energy and encourages Googlers as individuals to conserve energy. Google's search engine runs on open source software, and so Google as a company open sources its software and encourages Googlers to participate in existing open source projects.

What may be less obvious is that Google's search engine runs on ideas. Google as a company has a great Research department, but it also encourages Googlers to participate in the research community - both in visible, obvious ways like writing papers and attending conferences, but also in less visible but still necessary chores that keep the research community running, like reviewing papers and organizing conferences. What I'd like to tell you about today is how Google helped me give back to the research community by letting me take time to write a paper on work I did before I came to Google.

The Personal Pet Project
Ashwin Ram's Cognitive Computing Lab at Georgia Tech has been working on emotional agents for over ten years, first with robots, and more recently in computer games and virtual environments. I worked on one of our earliest efforts in this area, the PEPE (Personal Pet) project, a joint effort with Yamaha to develop an robotic pet. Dr. Ram noticed that many consumer electronics require configuration steps that are frustrating, even baffling: everything from VCRs to toasters has blinking clocks and unused features. Pets, on the other hand, don't have to be "configured": they understand us on emotional level, noticing what makes us happy or angry, remembering what brings reward and punishment, and learning to respond appropriately without us reading a manual or pushing a button.

PEPE emulated this intuitive understanding with an emotional long term memory module, which I developed. This module had three parts: basic emotions, emotional memory, and emotional reminding. Basic emotions gave the robot realistic behavior "out of the box": for example, the robot interpreted being petted on the head as being pleasant, which made it want to socialize; it interpreted a kick to the rear as unpleasant, which made it want to hide. The emotional memory associated these primitive emotions with the people and objects the robot saw in its environment. Emotional reminding closed the loop: when the robot saw a person or object again, it was reminded of the past emotion, which influenced but did not determine the robot's ultimate emotional expression. So the robot naturally wanted to play with people who petted it and fled people who had kicked it in the past, but it would be possible to overcome that past learning by ignoring the robot (if you didn't want to play with it as much anymore) or by petting it (if you had kicked it but no longer wanted it to be scared of you).

I worked with a team of engineers at Yamaha in Japan to implement this emotional long term memory on a small robot they were building. Our job was easier because PEPE's basic architecture enabled creating many different kinds of behaviors that could easily interact with each other, in parallel or in sequence. On top of this architecture, we added basic emotions, emotional learning and emotional reminding in stages. Our initial tests were positive, and upon my return to the United States, we began porting this software back to Georgia Tech's PEPE robot. PEPE even had a brief moment of fame, appearing on a local TV station; ultimately, however, Georgia Tech and Yamaha decided to move on to new projects.

Characters with Personality
But the dream of emotional agents didn't die. Manish Mehta, a graduate student at Georgia Tech researching interactive games, began working with Ram to try to develop more sophisticated models of emotional change. Mehta realized that emotional events can act as a trigger for behavioral change: if we humans try something that works really poorly, or spectacularly well, the emotions generated by that experience can prompt us to make changes to our behavior in the future --- for example, remembering to bring that umbrella in the future so we no longer have to walk home wet in the rain.

Mehta used ABL, an agent language developed by Michael Mateas and Andrew Stern for the Facade project. Like the fundamental architecture of PEPE, ABL enabled the author of an agent to design complicated behaviors that could interact in sequence, in parallel, or through complex triggering. Mehta extended ABL to allow an agent to rewrite its own behaviors, and triggered that rewriting based on charged emotional events. This worked: using two agents playing tag, Mehta was able to make them revise their behaviors based on how well they played the game. However, it had an unintended consequence: one of the agents decided it was less stressed out when it was "IT". When it was "IT", it wasn't being chased and wasn't feeling stressed, so it just let itself get tagged, enabling it to "chase" the other player at a leisurely pace.

While this result was surprising, even amazing, it failed to achieved the original objective. Mehta realized this had exposed one more property of human behavioral change: emotional events can prompt change, but we also have a self image - a model of what we think our personality should be like. As our personalities change, we audit the changes to make sure they fit our self image and apply further corrections. For a computer game character, that "personality" is really the designer's intent, so Mehta augmented his emotional learning system to check potential behavioral changes and make sure that they did not violate the original intended design. With this change, both characters were able to learn from their good and bad experiences playing tag, and neither "quit playing the game" just because they didn't want the stress of being chased.

Putting It All Together
The paper that Ram, and Mehta and I wrote for the Handbook of Synthetic Emotions and Sociable Robotics reports this work and ties together all of these threads. We were not alone in challenges we faced in developing intelligent agents: others faced them too, in robotics, computer games and academic AI. Many people use flexible behavior systems like PEPE's architecture or like ABL, but building large systems out of these can be challenging and extremely labor intensive. What Mehta and I found, however, is that the use of emotion models acted like a force multiplier: adding basic emotional responses to an existing behavior system radically increased the flexibility and apparent realism of an intelligent agent, whether it was a robotic puppy or a character in a computer game.

Moreover, the more components of the emotion stack you add to an agent, the easier it becomes to extend. While adding emotion made PEPE extended the behaviors it could perform; modifying those emotions using memories changed the character of its behavior, making it seem more lifelike. Mehta's work in extending ABL took this further, enabling creative behavior changes in response to agent frustration. Adding personality models makes these changes stable, enabling the agent to adapt to new situations while staying consistent with their designer's intent. Often, just adding more behaviors to an existing agent can make it more brittle; we found in contrast adding new layers inspired by research in human and animal emotion made the agent more sophisticated and robust.

Giving Something Back
Writing this paper did not take much time from Google. Most of it was done in the evening on my own time, with the occasional email exchange with my coauthors and editors during the day while I was waiting on compiles. And that is how it should be: it may be a long time before this work directly benefits Google, since we do not currently develop robots or computer games. But Google still benefited because the advances that we need to improve our search engine often start in academia.

By encouraging our staff to follow up on their research work and to contribute to the research community, Google supports the growth of the next big idea. Knowing that we can follow up on our past work makes researchers at Google feel more empowered to pursue new ideas and continually exposes us to sources of inspiration. And that inspiration, which makes Google a better place to work, is exactly what I need to keep trying new ideas, which in the end will help make Google a better place to search.