Monika Henzinger
Research Director

Monika Henzinger is a Research Director at Google Inc., working in the area of Web Information Retrieval and efficient algorithms and data structures. She graduated with a Ph.D. from Princeton University in 1993. Before joining Google she was an assistant professor at Cornell University, Ithaca, NY, and a research scientist at DEC Systems Research Center in Palo Alto, CA.

Monika has served on the program committee of STOC, FOCS, SODA, ICALP, STACS, and DM and has been a reviewer for SIGIR and the World Wide Web Conference. She has given invited talks at FOCS, ISAAC, ICDE, COLT, ESA, Supercomputing, DM, Cluster, PODS, ICALP, the NAA Sackler Colloquium and the Siemens International User Conference.

Monika received a NSF Young Investigator Award in 1995 and a Top 25 Women on the Web Award in 2001. Together with her co-authors she received a best paper award at SOSP 1997.

Publications:

• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time [HTML]
  SIAM Journal on Comp. 21(6):1184--1192, 1992.
  Brandon Dixon, Monika Rauch, and Robert E. Tarjan.

• Continuous Profiling: Where Have All the Cycles Gone? [HTML]
  ACM Transactions on Computer Systems, 15(4):357--390, 1997.
  Jennifer Anderson, Lance Berc, Jeff Dean, Sanjay Ghemawat, Monika R. Henzinger, Shun-Tak Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger, and William Weihl.
  

• Faster Shortest-Path Algorithms for Planar Graphs [PostScript]
  Special Issue of Journal of Computer and System Sciences on Selected Papers of STOC 1994, 55(1):3--23, 1997.
  Monika R. Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian

• The Connectivity Server: Fast Access to Linkage Information on the Web
  Proc. 7th International World Wide Web Conference, 1998, pages 469--477
  Krishna Bharat, Andrei Broder, Monika R. Henzinger, Puneet Kumar, and Suresh Venkatasubramanian

• Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology
  Algorithmica 24:1--13, 1999.
  Monika Rauch Henzinger, Valerie King, and Tandy Warnow

• Finding Related Web Pages in the World Wide Web
  Proc. 8th International World Wide Web Conference, 1999, pages 389--401.
  Jeffrey Dean and Monika R. Henzinger

• Measuring Search Engine Quality using Random Walks on the Web [HTML]
  Proc. 8th International World Wide Web Conference, 1999, pages 213--225
  Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, and Mark Najork

• Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation [PDF]
  Journal of the ACM, 46(4):502--516, 1999.
  Monika Rauch Henzinger and Valerie King

• Computing Vertex Connectivity: New Bounds from Old Techniques
  Journal of Algorithms, 34(2):222-250, 2000.
  Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow

• Improved Data Structures for Fully Dynamic Biconnectivity [PDF]
  SIAM Journal on Comp., 29(6):1761--1815, 2000.

• Exploring Unknown Environments
  SIAM Journal on Comp., 29(4):1164--1188, 2000.
  Susanne Albers and Monika Rauch Henzinger

• Computing on Data Streams
  DIMACS Series in Discrete Mathematics and Theoretical Computer Science: `"External Memory Algorithms", 50:107--118, 2000.
  Monika R. Henzinger, Prabhakar Ragahavan, and Sridhar Rajagopalan.

• On near-uniform URL sampling [HTML]
  Proc. 9th International World Wide Web Conference}, 1999, pages 295--308.
  Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, and Marc Najork

• A Comparison of Techniques to Find Mirrored Hosts on the WWW
  Journal of the American Society for Information Science, 51(12):1114--1122, 2000.
  Krishna Bharat, Andrei Z. Broder, Jeffrey Dean, and Monika R. Henzinger

• Maintaining Minimum Spanning Forests in Dynamic Graphs [PostScript]
  SIAM Journal on Comp., 31(2):364--374, 2001
  Monika R. Henzinger and Valerie King

• Scheduling Data Transfers in a Network and the Set Scheduling Problem
  Journal of Algorithms, 48(2):314--332, 2003
  Ashish Goel, Monika R. Henzinger, Serge Plotkin, and Eva Tardos

• Who Links to Whom: Mining Linkage between Web Sites
  1st International Conference on Data Mining (ICDM) 51-58 (2001)
  Krishna Bharat, Bay-Wei Chang, Monika Rauch Henzinger, Matthias Ruhl
  Abstract

• Extracting Knowledge from the World Wide Web
  Proc. of the National Academy of Science, 2004.
  Monika Henzinger and Steve Lawrence

• Query-Free News Search [PDF]
  Proc. 12th World Wide Web Conference, 2003, pages 1--10. Also in special issue of WWWJ on selected papers of WWW 2003.
  Monika Henzinger, Bay-Wei Chang, Brian Milch, and Sergey Brin
  Abstract

Book Chapters:

• Algorithmic Aspects of Information Retrieval on the Web
  In Handbook of Massive Data Sets. J. Abello, P.M. Pardalos, M.G.C. Resende (eds.), Kluwer, 2001.
  Andrei Broder and Monika R. Henzinger

• Data Structures in Web Information Retrieval
  To appear in Handbook of Data Structures, CPC Press.