And the award goes to...

Tuesday, July 27, 2010 at 7/27/2010 06:28:00 PM



Google's very own Tushar Chandra along with his coauthors, Vassos Hadzilacos, and Sam Toueg, received the prestigious Dijkstra Prize in Distributed Computing at the ACM Symposium on Principles of Distributed Computing conference in Zürich. This award is given for outstanding papers that have had great impact on the theory and practice of distributed computing for over a decade.

Their papers introduced and precisely characterized the notion of unreliable failure detection in a distributed system:


Tushar currently works on large-scale machine learning and distributed systems at Google.

You can find more information about the award and the papers here.

Congratulations to Tushar, Vassos, and Sam!

Googlers receive multiple awards at the 2010 International Conference on Machine Learning

at 7/27/2010 04:13:00 PM



Googlers were recognized in three of the four paper awards at ICML 2010:

I feel a particular connection to this last paper as Rob and Yoram were members of technical staff and Erin a student intern at the department I headed at AT&T Labs when this work was done.

Congratulations to all!

Announcing our Q2 Research Awards

Thursday, July 22, 2010 at 7/22/2010 09:23:00 AM



We’re excited to announce the latest round of Google Research Awards, our program which identifies and supports full-time faculty pursuing research in areas of mutual interest. From a record number of submissions, we are funding 75 awards across 18 different areas—a total of more than $4 million.

The areas that received the highest level of funding for this round were systems and infrastructure, human computer interaction, multimedia and security. We also continue to develop more collaborations internationally. In this round, 26 percent of the funding was awarded to universities outside the U.S.

Here are some examples from this round of awards:

  • Jeremy Cooperstock, McGill University. A Spatialized Audio Map System for Mobile Blind Users (Geo/maps): A mobile audio system that provides location-based information, primarily for use by the blind and visually impaired communities.
  • Alexander Pretschner, Karlsruhe Institute of Technology, Germany. Towards Operational Privacy (Security and privacy): Provide a framework for precise semantic definitions in policies for domain-specific applications to give users a way to define the exact behaviour they expect from a system in application-specific contexts.
  • Erik Brynjolfsson, Massachusetts Institute of Technology. The Future of Prediction - How Google Searches Foreshadow Housing Prices and Quantities (Economics and market algortihms): How data from search engines like Google provide a highly accurate but simple way to predict future business activities.
  • Stephen Pulman, Oxford University Computing Laboratory. Automatic Generation of Natural Language Descriptions of Visual Scenes (Natural language processing): Develop a system that automatically generates a description of a visual scene.
  • Jennifer Rexford, Princeton. Rethinking Wide-Area Traffic Management (Software and hardware systems infrastructure): Drawing on mature techniques from optimization theory, design new traffic-management solutions where the hosts, routers, and management system cooperate in a more effective way.
  • John Quinn, Makerere University, Uganda. Mobile Crop Surveillance in the Developing World (Multimedia search and audio/video processing): A computer vision system using camera-enabled mobile devices to monitor the spread of viral disease among staple crops.
  • Allison Druin, University of Maryland. Understanding how Children Change as Searchers (Human-computer interaction): Do children change as searchers as they age? How do searchers typically shift between roles over time? If children change, how many of them become Power Searchers? If children don’t change, what roles do they typically demonstrate?
  • Ronojoy Adhikari, The Institute of Mathematical Sciences, India. Machine Learning of Syntax in Undeciphered Scripts (Machine learning): Devise algorithms that would learn to search for evidence of semantics in datasets such as the Indus script.

You can find the full list of this round’s award recipients here (pdf). More information on our research award program can be found on our website.

Google PhD Fellowships go international

Thursday, July 15, 2010 at 7/15/2010 08:49:00 AM



(Cross-posted from the Official Google Blog)

We introduced the Google Fellowship program last year in the United States to broaden our support of university research. The students who were awarded the 2009 fellowships were a truly impressive group, many having high profile internships this past summer and even a few with faculty appointments in the upcoming year.

Universities continue to be the source of some of the most innovative research in computer science, and in particular it’s the students that they foster who are the future of our field. This year, we’re going global and extending the fellowship program to Europe, Israel, China and Canada. We’re very happy to be continuing our support of excellence in graduate studies and offer our sincere congratulations to the following PhD students for receiving Google Fellowships in 2010:

Google European Doctoral Fellowships
  • Roland Angst, Google Europe Fellowship in Computer Vision (Swiss Federal Institute of Technology Zurich, Switzerland)
  • Arnar Birgisson, Google Europe Fellowship in Computer Security (Chalmers University of Technology, Sweden)
  • Omar Choudary, Google Europe Fellowship in Mobile Security (University of Cambridge, U.K.)
  • Michele Coscia, Google Europe Fellowship in Social Computing (University of Pisa, Italy)
  • Moran Feldman, Google Europe Fellowship in Market Algorithms (Technion - Israel Institute of Technology, Israel)
  • Neil Houlsby, Google Europe Fellowship in Statistical Machine Learning (University of Cambridge, U.K.)
  • Kasper Dalgaard Larsen, Google Europe Fellowship in Search and Information Retrieval (Aarhus University, Denmark)
  • Florian Laws, Google Europe Fellowship in Natural Language Processing (University of Stuttgart, Germany)
  • Cynthia Liem, Google Europe Fellowship in Multimedia (Delft University of Technology, Netherlands)
  • Ofer Meshi, Google Europe Fellowship in Machine Learning (The Hebrew University of Jerusalem, Israel)
  • Dora Spenza, Google Europe Fellowship in Wireless Networking (Sapienza University of Rome, Italy)
  • Carola Winzen, Google Europe Fellowship in Randomized Algorithms (Saarland University / Max Planck Institute for Computer Science, Germany)
  • Marek Zawirski, Google Europe Fellowship in Distributed Computing (University Pierre and Marie Curie / INRIA, France)
  • Lukas Zich, Google Europe Fellowship in Video Analysis (Czech Technical University, Czech Republic)
Google China PhD Fellowships
  • Fangtao Li, Google China Fellowship in Natural Language Processing (Tsinghua University)
  • Ming-Ming Cheng, Google China Fellowship in Computer Vision (Tsinghua University)
Google United States/Canada PhD Fellowships
  • Chong Wang, Google U.S./Canada Fellowship in Machine Learning (Princeton University)
  • Tyler McCormick, Google U.S./Canada Fellowship in Statistics (Columbia University)
  • Ashok Anand, Google U.S./Canada Fellowship in Computer Networking (University of Wisconsin)
  • Ramesh Chandra, Google U.S./Canada Fellowship in Web Application Security (Massachusetts Institute of Technology)
  • Adam Pauls, Google U.S./Canada Fellowship in Machine Translation (University of California, Berkeley)
  • Nguyen Dinh Tran, Google U.S./Canada Fellowship in Distributed Systems (New York University)
  • Moira Burke, Google U.S./Canada Fellowship in Human Computer Interaction (Carnegie Mellon University)
  • Ankur Taly, Google U.S./Canada Fellowship in Language Security (Stanford University)
  • Ilya Sutskever, Google U.S./Canada Fellowship in Neural Networks (University of Toronto)
  • Keenan Crane, Google U.S./Canada Fellowship in Computer Graphics (California Institute of Technology)
  • Boris Babenko, Google U.S./Canada Fellowship in Computer Vision (University of California, San Diego)
  • Jason Mars, Google U.S./Canada Fellowship in Compiler Technology (University of Virginia)
  • Joseph Reisinger, Google U.S./Canada Fellowship in Natural Language Processing (University of Texas, Austin)
  • Maryam Karimzadehgan, Google U.S./Canada Fellowship in Search and Information Retrieval (University of Illinois, Urbana-Champaign)
  • Carolina Parada, Google U.S./Canada Fellowship in Speech (Johns Hopkins University)
The students will receive fellowships consisting of full coverage of tuition, fees and stipend for up to three years. These students have been exemplary thus far in their careers, and we’re looking forward to seeing them build upon their already impressive accomplishments. Congratulations to all of you!

Our commitment to the digital humanities

Wednesday, July 14, 2010 at 7/14/2010 03:45:00 AM

Posted by Jon Orwant, Engineering Manager for Google Books, Magazines and Patents

(Cross-posted from the Official Google Blog)

It can’t have been very long after people started writing that they started to organize and comment on what was written. Look at the 10th century Venetus A manuscript, which contains scholia written fifteen centuries earlier about texts written five centuries before that. Almost since computers were invented, people have envisioned using them to expose the interconnections of the world’s knowledge. That vision is finally becoming real with the flowering of the web, but in a notably limited way: very little of the world’s culture predating the web is accessible online. Much of that information is available only in printed books.

A wide range of digitization efforts have been pursued with increasing success over the past decade. We’re proud of our own Google Books digitization effort, having scanned over 12 million books in more than 400 languages, comprising over five billion pages and two trillion words. But digitization is just the starting point: it will take a vast amount of work by scholars and computer scientists to analyze these digitized texts. In particular, humanities scholars are starting to apply quantitative research techniques for answering questions that require examining thousands or millions of books. This style of research complements the methods of many contemporary humanities scholars, who have individually achieved great insights through in-depth reading and painstaking analysis of dozens or hundreds of texts. We believe both approaches have merit, and that each is good for answering different types of questions.

Here are a few examples of inquiries that benefit from a computational approach. Shouldn’t we be able to characterize Victorian society by quantifying shifts in vocabulary—not just of a few leading writers, but of every book written during the era? Shouldn’t it be easy to locate electronic copies of the English and Latin editions of Hobbes’ Leviathan, compare them and annotate the differences? Shouldn’t a Spanish reader be able to locate every Spanish translation of “The Iliad”? Shouldn’t there be an electronic dictionary and grammar for the Yao language?

We think so. Funding agencies have been supporting this field of research, known as the digital humanities, for years. In particular, the National Endowment for the Humanities has taken a leadership role, having established an Office of Digital Humanities in 2007. NEH chairman Jim Leach says: "In the modern world, access to knowledge is becoming as central to advancing equal opportunity as access to the ballot box has proven to be the key to advancing political rights. Few revolutions in human history can match the democratizing consequences of the development of the web and the accompanying advancement of digital technologies to tap this accumulation of human knowledge."

Likewise, we’d like to see the field blossom and take advantage of resources such as Google Books that are becoming increasingly available. We’re pleased to announce that Google has committed nearly a million dollars to support digital humanities research over the next two years.

Google’s Digital Humanities Research Awards will support 12 university research groups with unrestricted grants for one year, with the possibility of renewal for an additional year. The recipients will receive some access to Google tools, technologies and expertise. Over the next year, we’ll provide selected subsets of the Google Books corpus—scans, text and derived data such as word histograms—to both the researchers and the rest of the world as laws permit. (Our collection of ancient Greek and Latin books is a taste of corpora to come.)

We've given awards to 12 projects led by 23 researchers at 15 universities:
  • Steven Abney and Terry Szymanski, University of Michigan. Automatic Identification and Extraction of Structured Linguistic Passages in Texts.
  • Elton Barker, The Open University, Eric C. Kansa, University of California-Berkeley, Leif Isaksen, University of Southampton, United Kingdom. Google Ancient Places (GAP): Discovering historic geographical entities in the Google Books corpus.
  • Dan Cohen and Fred Gibbs, George Mason University. Reframing the Victorians.
  • Gregory R. Crane, Tufts University. Classics in Google Books.
  • Miles Efron, Graduate School of Library and Information Science, University of Illinois. Meeting the Challenge of Language Change in Text Retrieval with Machine Translation Techniques.
  • Brian Geiger, University of California-Riverside, Benjamin Pauley, Eastern Connecticut State University. Early Modern Books Metadata in Google Books.
  • David Mimno and David Blei, Princeton University. The Open Encyclopedia of Classical Sites.
  • Alfonso Moreno, Magdalen College, University of Oxford. Bibliotheca Academica Translationum: link to Google Books.
  • Todd Presner, David Shepard, Chris Johanson, James Lee, University of California-Los Angeles. Hypercities Geo-Scribe.
  • Amelia del Rosario Sanz-Cabrerizo and José Luis Sierra-Rodríguez, Universidad Complutense de Madrid. Collaborative Annotation of Digitalized Literary Texts.
  • Andrew Stauffer, University of Virginia. JUXTA Collation Tool for the Web.
  • Timothy R. Tangherlini, University of California-Los Angeles, Peter Leonard, University of Washington. Northern Insights: Tools & Techniques for Automated Literary Analysis, Based on the Scandinavian Corpus in Google Books.
We have selected these proposals in part because the resulting techniques, tools and data will be broadly useful: they’ll help entire communities of scholars, not just the applicants. We look forward to working with them, and hope that over time the field of digital humanities will fulfill its promise of transforming the ways in which we understand human culture.

Google launches Korean Voice Search

Wednesday, June 30, 2010 at 6/30/2010 02:45:00 PM



On June 16th, we launched our Korean voice search system. Google Search by Voice has been available in various flavors of English since 2008, in Mandarin and Japanese since 2009, and in French, Italian, German and Spanish just a few weeks ago (some more details in a recent blog post).

Korean speech recognition has received less attention than English, which has been studied extensively around the world by teams in both English and non-English speaking countries. Fundamentally, our methodology for developing a Korean speech recognition system is similar to the process we have used for other languages. We created a set of statistical models: an acoustic model for the basic sounds of the language, a language model for the words and phrases of the language, and a dictionary mapping the words to their pronunciations. We trained our acoustic model using a large quantity of recorded and transcribed Korean speech. The language model was trained using anonymized Korean web search queries. Once these models were trained, given an audio input, we can compute and display the most likely spoken phrase, along with its search result.

There were several challenges in developing a Korean speech recognition system, some unique to Korean, some typical of Asian languages and some universal to all languages. Here are some examples of problems that stood out:

  • Developing a Korean dictionary: Unlike English, where there are many publicly-available dictionaries for mapping words to their pronunciations, there are very few available for Korean. Since our Korean recognizer knows several hundred thousand words, we needed to create these mappings ourselves. Luckily, Korean has one of the most elegant and simple writing systems in the world (created in the 15th century!) and this makes mapping Korean words to pronunciations relatively straightforward. However, we found that Koreans also use quite a few English words in their queries, which complicates the mapping process. To predict these pronunciations, we built a statistical model using data from an existing (smaller) Korean dictionary.
  • Korean word boundaries: Although Korean orthography uses spaces to indicate word boundaries (unlike Japanese or Mandarin), we found that people use word boundaries inconsistently for search queries. To limit the size of the vocabulary generated from the search queries, we used statistical techniques to cut rare long words into smaller sub-words (similarly to the system we developed for Japanese).
  • Pronunciation exceptions: Korean (like all other languages) has many exceptions for pronunciations that are not immediately obvious. For example, numbers are often written as digit sequences but not necessarily spoken this way (2010 = 이천십). The same is true for many common alphanumeric sequences like “mp3”, “kbs2” or mixed queries like “삼성 tv”, which often contain spelled letters and possibly English spoken digits as opposed to Korean ones.
  • Encoding issues: Korean script (Hangul) is written in syllabic blocks, with each block containing at least two of the 24 modern Hangul letters (Jamo), at least one consonant and one vowel. Including the normal ASCII characters this brings the total number of possible basic characters to over 10000, not including Hanja (used mostly in the formal spelling of names). So, despite its simple writing system, Korean still presents the same challenge of handling a large alphabet that is typical of Asian languages.
  • Script ambiguity: We found that some users like to use English native words and others the Korean transliteration (example: “ncis season 6” vs. “ncis 시즌6”). This makes it challenging to train and evaluate the system. We use a metric that estimates whether our transcription will give the correct web page result on the user’s smart phone screen, and such script variations make this tricky.
  • Recognizing rare words: The recognizer is good at recognizing things users often type into the search engine, such as cities, shops, addresses, common abbreviations, common product model numbers and well-known names like “김연아”. However, rare words (like many personal names) are often harder for us to recognize. We continue to work on improving those.
  • Every speaker sounds different: People speak in different styles, slow or fast, with an accent or without, have lower or higher pitched voices, etc. To make our system work for all these different conditions, we trained our system using data from many different sources to capture as many conditions as possible.

When speech recognizers make errors, the reason is usually that the models are not good enough, and that often means they haven’t been trained on enough data. For Korean (and all other languages) our cloud computing infrastructure allows us to retrain our models frequently and using an ever growing amount of data to continually improve performance. Over time, we are committed to improve the system regularly to make speech a user-friendly input method on mobile devices.

Google Search by Voice now available in France, Italy, Germany and Spain

Monday, June 14, 2010 at 6/14/2010 04:00:00 PM



Google’s speech team is composed of people from many different cultural backgrounds. Indeed, if we count the languages spoken by our teammates, the number comes to well over a dozen. Given our own backgrounds and interests, we are naturally excited to extend our software to work with many different languages and dialects. After testing the waters with English, Mandarin Chinese, and Japanese, we decided to tackle four main European languages which are often referred to as FIGS - French, Italian, German and Spanish.

Developing Voice Search systems in each of these languages presented its own challenges. French and Spanish required special work to deal with diacritic and accent marks (e.g. ç in French, ñ in Spanish). When we develop a new language we tweak our dictionaries based on user generated content. To our surprise we found that a lot of this content in French and Spanish often uses non-standard orthography. For example a French speaker might type “francoise” into a search engine and still expect it to return results for “Françoise”. Likewise in Spanish a user might type “espana” and expect results for the term “España”. Of course a lot of this has to do with the fact that, until recently, domain names (like www.elpais.es) did not allow diacritics, and that entering special characters is often painful but omitting diacrictics is usually not an obstacle to communication. However, non-standard spellings distort the intended pronunciations. For example, if “francoise” were a real French word, one would expect it to be pronounced “franquoise”. In order to capture the intended pronunciation of the non-standard spellings, we fixed the orthography in our dictionaries for Spanish and French automatically. While this is not perfect, it deals with many of the offending cases.

Since our Voice search systems typically understand more than a million different words in each language, developing pronunciation dictionaries is one of the most critical tasks. We need the dictionary to match what the user said with the written form. Not surprisingly we found that dictionary development for some languages like Spanish and Italian to be extremely easy, as they have very regular orthographies. In fact the core of our Spanish pronunciation module consists of less than 100 lines of source code. Other languages like German and French have more complex orthographies. For example in French “au”, “eaux” and “hauts” are all pronounced “o”.

A notable aspect of German (especially “Internet German”) is that a lot of English words are in common usage. We do our best to recognize thousands of English words, even though English contains some sounds that don’t exist in German, like “th” in “the”. One of the trickiest examples we came across was when one of our volunteers read “nba playoffs 2009”, saying “nba playoffs” in English followed by “zwei tausend neun” in German. So go ahead and search for “Germany’s Next Topmodel” or “Postbank Online”, see if it works for you.

German is also notorious for having long, complex words. Our favorite examples include:


Just for fun, compare how long it takes you to say these to Voice Search vs. typing them.

Even though a vocabulary size of one million words sounds like a large number, each of these languages has even more words, so we need a procedure to select which ones to model. We obviously do not do this manually and instead use statistical procedures to identify the list of words we will allow. We do this by looking at many sources of data and looking at the frequency of words. It is therefore surprising to find sometimes really weird terms selected by our algorithms. For example in Spanish we found these unusual words:

So, in the unlikely event that you ever try a Spanish voice search query like this “imágenes del músculo supercalifragilisticoespialidoso chiripitiflautico esternocleidomastoideo” you may be surprised to see that it works.

French, Italian, German, and Spanish are spoken in many parts of the world. In this first release of Google Search by Voice in these languages, we initially only support the varieties spoken in France, Italy, Germany, and Spain, respectively. The reason is that almost all aspects of a Voice Search system are affected by regional variation: French speakers from different regions have slightly different accents, use a number of different words, and will want to search for different things. Eventually, we plan to support other regions as well, and we will work hard to make sure our systems work well for all of you.

So, we hope you find these new voice search system useful and fun to use. We definitely had a “supercalifragilisticoespialidoso chiripitiflautico” time developing them.