EECS Joint Colloquium Distinguished Lecture Series

Wednesday, February 04, 2004
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Dr. Monika Henzinger

Research Director,
Google Inc.


Algorithmic Problems in Web Information Retrieval




Dr. Henzinger describes three algorithmic problems arising in web information retrieval:

    • uniform sampling of web pages
        load balancing for parallel query processing
          query-free news search. Sampling pages from the World Wide Web uniformly at random is useful for estimating various properties of the web and of web search engines. Dr. Henzinger describes an approach based on random walks that achieves an approximately random sample. Maximizing throughput is important for a system that processes millions of user requests per day. Dr. Henzinger describes an improved load balancing algorithm for parallel query processing that significantly improves throughput. One of the nuisances of web search is that the user has to formulate a suitable query at a web search engine in order to find the pages he wants. Query-free search systems find web pages relevant to the user's current topic of attention without any searches by the user. Given the stream of text that the user currently reads, writes, or listens to, the system automatically extracts query terms, issues them to a suitable search engine, and postprocesses and presents the results. Dr. Henzinger presents a comparison of query extraction and postprocessing algorithms for query-free search from broadcast news.

  •     Biography:

    Monika Henzinger is director of research at Google Inc.,the award-winning search engine that uses next-generation search technology. Focusing her energies on how search innovations six to 12 months in the future, Henzinger oversees the development of all of Google’s search feature innovations. In 2000, she led the team effort that pioneered converting Internet html searches from the desktop into highly efficient wireless application protocol (WAP) searches for the cell phone and Palm handheld devices. And Henzinger is responsible for leading a fifteen-person team that continually strives to improve the quality of Google’s existing search features. Finally, Henzinger serves as Google’s liaison to the academic and industry communities. Prior to joining Google, Henzinger was a member of the research staff at Digital's Systems Research Center in Palo Alto, California. Henzinger received her Ph.D. from Princeton University in 1993 under the supervision of Robert E. Tarjan. In fall 1993 she joined the Computer Science Department at Cornell University as an assistant professor and received a National Science Foundation CAREER award in 1995. She is also a recipient of the Wallace Memorial Honorific Fellowship at Princeton University, the Studienstiftung des deutschen Volkes and the Siemens Scholarship awards.