Purely URL-based Topic Classification (2009)
Baykan, Eda, Henzinger, Monika R., Marian, Ludmila, Weber, Ingmar
Given only the URL of a web page, can we identify its topic? This is the question that we examine in this paper. Usually, web pages are classified using their content, but a URL-only classifier is...
Detecting the Origin of Text Segments Efficiently (2009)
Abdel-Hamid, Ossama, Behzadi, Behshad, Christoph, Stefan, Henzinger, Monika R.
In the origin detection problem an algorithm is given a set S of documents, ordered by creation time, and a query document D. It needs to output for every consecutive sequence of k alphanumeric terms...
[12] Internet Performance Measurement and Analysis (2008)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, Shun-tak A, ...
design. We would like to thank Sally Floyd for her help with the BGP TCP analysis. Finally, we thank Gary Delp and the anonymous SIGCOMM ‘98 reviewers for their helpful and constructive comments.
article no. SS971493 Faster Shortest-Path Algorithms for Planar Graphs (2008)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Krishna Bharat, Andrei Broder, Monika R. Henzinger, Jeffrey Dean
We compare several algorithms for identifying mirrored hosts on the World Wide Web. The algorithms operate on the basis of URL strings and linkage data: the type of information about web pages easily...
Ashish Goel, Monika R. Henzinger, Google Inc, Serge Plotkin, Eva Tardos
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Monika R. Henzinger, Rajeev Motwani
This article presents a high-level discussion of some problems in information retrieval that are unique to web search engines. The goal is to raise awareness and stimulate research in these areas. 1
Algorithmic Challenges in Web Search Engines (2003)
In this paper, we describe six algorithmic problems that arise in web search engines and that are not or only partially solved: (1) Uniformly sampling of web pages; (2) modeling the web graph; (3)...
Challenges in web search engines (2003)
Abstract. In this paper, we describe six algorithmic problems that arise in web search engines and that are not or only partially solved: (1) Uniformly sampling of web pages; (2) modeling the web...
Challenges in web search engines (2002)
Henzinger, Monika R., Motwani, Rajeev, Silverstein, Craig
This article presents a high-level discussion of some problems in information retrieval that are unique to web search engines. The goal is to raise awareness and stimulate research in these areas.
Maintaining minimum spanning forests in dynamic graphs (2001)
Monika R. Henzinger, Valerie King
Abstract. We present the first fully dynamicalgorithm for maintaining a minimum spanning forest in time o ( √ n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per...
Scheduling data transfers in a network and the set scheduling problem (1999)
Goel, Ashish, Henzinger, Monika R., Plotkin, Serge, Tardos, Eva
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Scheduling multicasts on unit-capacity trees and meshes (1999)
Henzinger, Monika R., Leonardi, Stefano
This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput-model. The problem is a generalization of the edge-disjoint paths...
Measuring index quality using random walks on the web (1999)
Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork
Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...
Measuring index quality using random walks on the web (1999)
Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork
Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...
Scheduling data transfers in a network and the set scheduling problem (1999)
Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos
In this paper we consider the online ftp problem. The goal is to service a sequence of le transfer requests given bandwidth constraints of the underlying communication network. The main result of the...
Measuring Index Quality using Random Walks on the Web (1999)
Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork
Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a different measure for search engines, namely the quality...
Scheduling Data Transfers in a Network and the Set Scheduling Problem (1999)
Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
A Comparison of Techniques to Find Mirrored Hosts on the WWW (1999)
Krishna Bharat, Andrei Broder, Jeffrey Dean, Monika R. Henzinger
We compare several algorithms for identifying mirrored hosts on the World Wide Web. The algorithms operate on the basis of URL strings and linkage data: the type of information easily available from...
Scheduling Data Transfers in a Network and the Set Scheduling Problem (1999)
Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Finding Related Pages in the World Wide Web (1999)
Jeffrey Dean, Monika R. Henzinger
When using traditional search engines, users have to formulate queries to describe their information need. This paper discusses a different approach to web searching where the input to the search...
Scheduling data transfers in a network and the set scheduling problem (1999)
Ashish Goel, Monika R. Henzinger, Serge Plotkin
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Scheduling Multicasts on Unit-Capacity Trees and Meshes (1999)
Stefano Leonardi, Monika R. Henzinger, Monika R. Henzinger
This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput-model. The problem is a generalization of the edge-disjoint paths...
Measuring index quality using random walks on the web (1999)
Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork
Recent research has studied how to measure the size of a search engine, in terms of the number of pages indexed. In this paper, we consider a di erent measure for search engines, namely the quality...
ALGORITHMS FOR NETWORK ROUTING, MULTICASTING, SWITCHING, AND DESIGN (1999)
Monika R. Henzinger, Rajeev Motwani
as a dissertation for the degree of Doctor of Philosophy.
Scheduling data transfers in a network and the set scheduling problem (1999)
Ashish Goel, Monika R. Henzinger, Serge Plotkin
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Randomized fully dynamic graph algorithms with polylogarithmic time per operation (1999)
Monika R. Henzinger, Valerie King
Abstract. This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum...
Parametric and kinetic minimum spanning trees (1998)
Agarwal, Pankaj K., Eppstein, David, Guibas, Leonidas J., Henzinger, Monika R.
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter, and wish to computethe sequence of minimum spanning...
Improved algorithms for topic distillation in a hyperlinked environment (1998)
Bharat, Krishna, Henzinger, Monika R.
This paper addresses the problem of topic distillation on the World Wide Web, namely, given a typical user query to find quality documents related to the query topic. Connectivity analysis has been...
Online throughput-competitive algorithm for multicast routing and admission control (1998)
Goel, Ashish, Henzinger, Monika R., Plotkin, Serge
We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...
Online throughput-competitive algorithm for multicast routing and admission control (1998)
Ashish Goel, Monika R. Henzinger, Serge Plotkin
We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...
Scheduling Data Transfers in a Network and the Set Scheduling Problem (1998)
Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Parametric and Kinetic Minimum Spanning Trees (1998)
Pankaj Agarwal David, Leonidas J. Guibas, Monika R. Henzinger
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter # and wish to compute the sequence of minimum...
Parametric and Kinetic Minimum Spanning Trees (1998)
Pankaj Agarwal, David Eppstein, Leonidas J. Guibas, Monika R. Henzinger
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter # and wish to compute the sequence of minimum...
Scheduling Data Transfers in a Network and the Set Scheduling Problem (1998)
Ashish Goel, Monika R. Henzinger, Serge Plotkin, Eva Tardos
In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of...
Improved Algorithms for Topic Distillation in a Hyperlinked Environment (1998)
Krishna Bharat, Monika R. Henzinger
This paper addresses the problem of topic distillation on the World Wide Web, namely, given a typical user query to find quality documents related to the query topic. Connectivity analysis has been...
An Online Throughput-Competitive Algorithm For Multicast Routing And Admission Control (1998)
Ashish Goel, Monika R. Henzinger, Serge Plotkin
. We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...
Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control (1998)
Ashish Goel, Monika R. Henzinger, Serge Plotkin
We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to...
Online throughput-competitive algorithm for multicast routing and admission control (1998)
Ashish Goel, Monika R. Henzinger, Google Inc, Serge Plotkin
We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the...
Exploring unknown environments (1997)
Albers, Susanne, Henzinger, Monika R.
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Continuous Profiling: Where Have All the Cycles Gone (1997)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Continuous Profiling: Where Have All the Cycles Gone? (1997)
Jennifer M. Anderson, Lance M. BERC, Jeffrey Dean, MONIKA R. HENZINGER, RICHARD L. SITES, ...
This article describes the Digital Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors,...
Exploring Unknown Environments (1997)
Susanne Albers Monika, Monika R. Henzinger
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Systems Research Center, Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Continuous Profiling: Where Have All the Cycles Gone? (1997)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Continuous Profiling: Where Have All the Cycles Gone? (1997)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Exploring Unknown Environments (1997)
Susanne Albers, Monika R. Henzinger, R. Henzinger
. We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Exploring Unknown Environments (1997)
Susanne Albers, Monika R. Henzinger
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The...
Maintaining Minimum Spanning Trees in Dynamic Graphs (1997)
Monika R. Henzinger, Valerie King
. We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o( p n) per operation. To be precise, the algorithm uses O(n 1=3 log n) amortized time per update...
Continuous Profiling: Where Have All the Cycles Gone (1997)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Continuous Profiling: Where Have All the Cycles Gone (1997)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Continuous Profiling: Where Have All the Cycles Gone (1997)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, ...
This paper describes the DIGITAL Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works...
Computing vertex connectivity: New bounds from old techniques (1996)
Henzinger, Monika R., Rao, Satish, Gabow, Harold N.
The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the...
Computing Simulations on Finite and Infinite Graphs (1996)
Monika R. Henzinger, Thomas A. Henzinger, Peter W. Kopke
. We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we...
Dynamic Graph Algorithms (1996)
Monika R. Henzinger, Mikkel Thorup, Monika R. Henzinger, Mikkel Thorup
The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support...
Monika R. Henzinger, Satish Rao, Harold N. Gabow
The vertex connectivity � of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the...
Dynamic Graph Algorithms (1996)
Monika R. Henzinger, Mikkel Thorup, Monika R. Henzinger, Mikkel Thorup
The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support...
Computing Simulations on Finite and In nite Graphs y (1996)
Monika R. Henzinger, Thomas A. Henzinger, Peter W. Kopke
Abstract. We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the re nement and veri cation of reactive systems. For nite graphs, we...
Computing simulations on finite and infinite graphs (1995)
Henzinger, Monika R., Henzinger, Thomas A., Kopke, Peter W.
We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we...
Computing Simulations on Finite and Infinite Graphs (1995)
Monika R. Henzinger, Thomas A. Henzinger, Peter W. Kopke
. We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we...
Computing simulations on finite and infinite graphs (1995)
Monika R. Henzinger, Thomas A. Henzinger, Peter W. Kopke
Abstract. We present algorithms for computing similar-ity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reac-tive systems. For finite...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Improved data structures for fully dynamic biconnectivity (1994)
Abstract. We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and...
To Provide or To Bound: Sampling in Fully Dynamic Graph Algorithms (1991)
Monika R. Henzinger And Mikkel Thorup, Monika R. Henzinger, Monika R. Henzinger, Mikkel Thorup, Mikkel Thorup
In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership...
[12] Internet Performance Measurement and Analysis (1989)
Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, Shun-tak A, ...
Polyzos. A parameterizable methodology for Internet traffic