THE ELECTRICAL RESISTANCE OF A GRAPH CAPTURES ITS COMMUTE AND COVER TIMES (2009)
Ashok K. Ch, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari
Abstract. View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that...
Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, Prabhakar Raghavan
story scheduling in web advertising
David Liben-nowell, Ravi Kumar, Prabhakar Raghavan, Jasmine Novak, Andrew Tomkins
We live in a “small world, ” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively...
David Gibson, Prabhakar Raghavan, Jon Kleinberg
The World Wide Web grows through a decentralized, almost anarchic process, and this has resulted in a large hyperlinked corpus without the kind of logical organization that can be built into more...
Jon Kleinberg, Prabhakar Raghavan
Abstract. We study a novel genre of optimization problems, which we call segmentation problems, motivated in part by certain aspects of clustering and data mining. For any classical optimization...
() 1994 Society for Industrial and Applied Mathematics (2008)
Andrei Z. Broder, Anna R. Karlint, Prabhakar Raghavan, Eli Upfal
undirected graphs can be solved in log space and O(mn) time [m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and...
Graph structure in the web Graph structure in the web (2008)
Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, ...
The study of the web as a graph is not only fascinating in its own right, but also yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological...
www9 paper Graph structure in the web (2008)
Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Raymie Stata, Andrew Tomkins, ...
The study of the web as a graph is not only fascinating in its own right, but also yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological...
Abstract Auditing Boolean Attributes (2008)
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
We study the problem of auditing databases which support statistical sum queries to protect the security of sensitive information; we focus on the special case in which the sensitive information is...
ABSTRACT On the Bursty Evolution of Blogspace (2008)
Ravi Kumar, Prabhakar Raghavan, Jasmine Novak, Andrew Tomkins
We propose two new tools to address the evolution of hyperlinked corpora. First, we define time graphs to extend the traditional notion of an evolving directed graph, capturing link creation as a...
IEEE J. ON SELECT. AREAS COMMUN. 1 Building Low-Diameter Peer-to-Peer Networks (2008)
Gopal P, Prabhakar Raghavan, Eli Upfal
Abstract—Peer-to-Peer (P2P) computing has emerged as a significant paradigm for providing distributed services, in particular search and data sharing. Current P2P networks (e.g., Gnutella) are...
Mining Significant Associations in Large Scale Text Corpora (2008)
Prabhakar Raghavan, Verity Inc, Panayiotis Tsaparas
Mining large-scale text corpora is an essential step in extracting the key themes in a corpus. We motivate a quantitative measure for significant associations through the distributions of pairs and...
David Gibson, Prabhakar Raghavan, Jon Kleinberg
We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data. By \categorical data, " we mean tables with elds that...
Abstract Stochastic Contention Resolution With Short Delays (2008)
Prabhakar Raghavan, Eli Upfalt
We study contention resolution protocols under a sto-chastic model of continuous request generation from a set of contenders. The performance of such a proto-col is characterized by two parameters:...
Brian D. Davison, Apostolos Gerasoulis, Konstantinos Kleisouris, Yingfang Lu, Hyun-ju Seo, Junyu Tian, ...
Recently the notion of popularity and its generalizations have been investigated as a possible alternative approach to text only analysis to rank web pages in search engines (e.g. [Kle98, BP98, CDR +...
Mani Abrol, Neil Latarche, Uma Mahadevan, Jianchang Mao, Rajat Mukherjee, Prabhakar Raghavan, ...
large-scale semi-structured data in business portals
ABSTRACT Visualizing Tags over Time (2008)
Micah Dubinko, Ravi Kumar, Joseph Magnani, Jasmine Novak, Prabhakar Raghavan, Andrew Tomkins
We consider the problem of visualizing the evolution of tags within the Flickr (flickr.com) online image sharing community. Any user of the Flickr service may append a tag to any photo in the system....
Mani Abrol, Neil Latarche, Uma Mahadevan, Jianchang Mao, Rajat Mukherjee, Prabhakar Raghavan, ...
large-scale semi-structured data in business portals
Query Strategies for Priced Information (Extended Abstract) (2007)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Lydia Kavraki, Jean-claude Latombe, Tsai-yen Li, Rajeev Motwani, Prabhakar Raghavan
Several randomized path planners have been proposed over the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empirically observed...
Soumen Chakrabarti, Byron E. Dom, David Gibson, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
We develop a technique we call spectral filtering, for discovering high-quality topical resources in hyperlinked corpora. Through relevance and quality judgements collected from 37 users, we show...
Lydia Kavraki, Jean-claude Latombe, Tsai-yen Li, Rajeev Motwani, Prabhakar Raghavan
Several randomized path planners have been proposed over the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empirically observed...
Soumen Chakrabarti, Byron E. Dom, Prabhakar Raghavan, Sridhar Rajagopalan, David Gibson, Konstantinos Kleisouris, ...
[Kle98] Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. In
Soumen Chakrabarti, Byron Dom, Rakesh Agrawal, Prabhakar Raghavan
Abstract. We explore how to organize large text databases hierarchically by topic to aid better searching, browsing and filtering. Many corpora, such as internet directories, digital libraries, and...
ABSTRACT The Web as a graph (2007)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew S. Tomkins, Eli Upfal
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow...
Paul Beame, Paul Beame, Allan Borodin, Allan Borodin, Prabhakar Raghavan, Prabhakar Raghavan, ...
We prove time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff 's "Jumping Automata for Graphs"....
On a Theory of Computing Symposia (2007)
Avrim Blum, Prabhakar Raghavan
We consider the problem of scheduling a conference to achieve the benefits in timecompression of parallel sessions, but without the associated high degree of conflict between talks. We describe a...
Journal Of Computer, Lydia E. Kavraki, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan
The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general...
Motion Planning for a Steering-Constrained Point Robot through Moderate Obstacles (2007)
Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki
Most mobile robots use steering mechanisms to guide their motion. Such mechanisms have stops that constrain the rate at which the robot can change its direction. We study a point robot in the plane...
ABSTRACT The Web as a graph (2007)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow...
Prabhakar Raghavan, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, Eli Upfal
The web may be viewed as a directed graph each of whose vertices is a static HTML web page, and each of whose edges corresponds to a hyperlink from one web page to another. In this paper we propose...
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's "Jumping Automata for Graphs". 3
Moses Charikar, Ronald Fagin, Venkatesan Gu-uswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
oo22-oooOl02 $35.00
Lydia E. T{avraki, Prabhakar Raghavan
RAJEEV MOTWANI t The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems...
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Monika Rauch Henzinger, Prabhakar Raghavan
In this paper we study the space requirement of algorithms that make only one (or a small number of) pass(es) over the input data. We study such algorithms under a model of data streams that we...
Peter Doyle, Prabhakar Raghavan, Marc Snir
We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges. We...
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal
Building P2P networks with good topological properties
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
We introduce backoff processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the "back button. " With...
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, David P. Williamson
We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic...
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal
Recent work on modeling the Web graph has dwelt on capturing the degree distributions observed on the Web. Pointing out that this represents a heavy reliance on \local " properties of the...
Random Walks with \Back Buttons" (2007)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
We introduce backo processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the \back button. " With some...
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Stochastic models for the web graph Ravi Kumar (2007)
Prabhakar Raghavan, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, Eli Upfal
The web may be viewed as a directed graph each of whose vertices is a static HTML web page, and each of whose edges corresponds to a hyperlink from one web page to another. In this paper we propose...
Jon Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan
As individuals increasingly take advantage of on-line services, the value of the private information they possess emerges as a problem of fundamental concern. We believe that the principle underlying...
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, ...
k+1 n Algorithm for k-SAT
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, David P. Williamson
We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic...
Mining Significant Associations in Large Scale Text Corpora (2007)
Prabhakar Raghavan Verity, Prabhakar Raghavan, Verity Inc, Panayiotis Tsaparas
Mining large-scale text corpora is an essential step in extracting the key themes in a corpus. We motivate a quantitative measure for significant associations through the distributions of pairs and...
Efficiency-Quality Tradeoffs for Vector Score Aggregation (2007)
Pavan Kumar, C. Singitham, Mahathi S. Mahabhashyam, Prabhakar Raghavan
Finding the ℓ nearest neighbors to a query in a vector space is an important primitive in text and image retrieval. Here we study an extension of this problem with applications to XML and image...
Theoretical Analysis of Geographic Routing in Social Networks (2005)
Kumar, Ravi, Liben-Nowell, David, Novak, Jasmine, Raghavan, Prabhakar, Tomkins, Andrew
We introduce a formal model for geographic social networks, and introduce the notion of rank-based friendship, in which the probability that a person v is a friend of a person u is inversely...
Theoretical Analysis of Geographic Routing in Social Networks (2005)
Kumar, Ravi, Liben-Nowell, David, Novak, Jasmine, Raghavan, Prabhakar, Tomkins, Andrew
We introduce a formal model for geographic social networks, and introduce the notion of rank-based friendship, in which the probability that a person v is a friend of a person u is inversely...
Query Incentive Networks (2005)
Jon Kleinberg, Prabhakar Raghavan
The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding...
Automatic Subspace Clustering of High Dimensional Data (2005)
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, Prabhakar Raghavan
Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user...
Query Incentive Networks (2005)
Jon Kleinberg Prabhakar, Prabhakar Raghavan
The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding...
Variable latent semantic indexing (2005)
Anirban Dasgupta, Prabhakar Raghavan, Andrew Tomkins
Latent Semantic Indexing is a classical method to produce optimal low-rank approximations of a term-document matrix. However, in the context of a particular query distribution, the approximation thus...
Data Mining: The Next Generation (2005)
Ramakrishnan, Raghu, Agrawal, Rakesh, Freytag, Johann-Christoph, Bollinger, Toni, Clifton, Christopher W., Dzeroski, Saso, ...
Data Mining (DM) has enjoyed great popularity in recent years, with advances in both research and commercialization. The first generation of DM research and development has yielded several...
Propagation of Trust and Distrust (2004)
Guha, R, Kumar, Ravi, Raghavan, Prabhakar, Tomkins, Andrew
A (directed) network of people connected by ratings or trust scores, and a model for propagating those trust scores, is a fundamental building block in many of today’s most successful e-commerce...
Anti-Aliasing on the Web (2004)
Novak, Jasmine, Raghavan, Prabhakar, Tomkins, Andrew
It is increasingly common for users to interact with the web using a number of different aliases. This trend is a doubleedged sword. On one hand, it is a fundamental building block in approaches to...
Propagation of Trust and Distrust (2004)
R. Guha, Prabhakar Raghavan, Andrew Tomkins
A network of people connected by directed ratings or trust scores, and a model for propagating those trust scores, is a fundamental building block in many of today’s most successful e-commerce and...
Propagation of Trust and Distrust (2004)
A (directed) network of people connected by ratings or trust scores, and a model for propagating those trust scores, is a fundamental building block in many of today’s most successful e-commerce...
On the bursty evolution of Blogspace (2003)
Kumar, Ravi, Novak, Jasmine, Raghavan, Prabhakar, Tomkins, Andrew
We propose two new tools to address the evolution of hyperlinked corpora. First, we define time graphs to extend the traditional notion of an evolving directed graph, capturing link creation as a...
Symphony: Distributed hashing in a small world (2003)
Gurmeet Singh Manku, Mayank Bawa, Prabhakar Raghavan, Verity Inc
We present Symphony, a novel protocol for maintaining distributed hash tables in a wide area network. The key idea is to arrange all participants along a ring and equip them with long distance...
More on Random Walks, Electrical Networks, and the Harmonic k-Server Algorithm (2003)
Yair Bartal, Marek Chrobak, John Noga, Prabhakar Raghavan
Techniques from electrical network theory have been used to establish various properties of random walks. We explore this connection further, by showing how the classical formulas for the determinant...
Gopal Pandurangan Member, Gopal P, Prabhakar Raghavan, Eli Upfal
Peer-to-Peer (P2P) computing has emerged as a significant paradigm for providing distributed services, in particular search and data sharing. Current P2P networks (e.g., Gnutella) are constructed by...
ABSTRACT SETS: Search Enhanced by Topic Segmentation (2003)
Mayank Bawa, Gurmeet Singh Manku, Prabhakar Raghavan
We present SETS, an architecture for efficient search in peer-to-peer networks, building upon ideas drawn from machine learning and social network theory. The key idea is to arrange participating...
SETS: Search Enhanced by Topic Segmentation (2003)
Mayank Bawa, Gurmeet Singh Manku, Prabhakar Raghavan
We present SETS, an architecture for efficient search in peer-to-peer networks, building upon ideas drawn from machine learning and social network theory. The key idea is to arrange participating...
Social Networks for Enterprise Webs (2002)
Abrol, Mani, Mahadevan, Uma, McCracken, Kenneth, Mukherjee, Rajat, Raghavan, Prabhakar
Using PageRank to Characterize Web Structure (2002)
Gopal Pandurangan Prabhakar, Gopal P, Prabhakar Raghavan, Eli Upfal
Recent work on modeling the Web graph has dwelt on capturing the degree distributions observed on the Web. Pointing out that this represents a heavy reliance on "local" properties of the...
Random walks with ``back buttons'' (2001)
Fagin, Ronald, Karlin, Anna R., Kleinberg, Jon, Raghavan, Prabhakar, Rajagopalan, Sridhar, Rubinfeld, Ronitt, ...
We introduce backoff processes, an idealized stochastic model of browsing on the World Wide Web, which incorporates both hyperlink traversals and use of the “back button.” With some probability...
Random walks with "back buttons". Annals of Applied Probability (2001)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
y We introduce backoff processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the "back button. " With...
On semi-automated web taxonomy construction (2001)
Ravi Kumar, Prabhakar Raghavan, Ý Sridhar, Rajagopalan Andrew Tomkins
The subject of this paper is the semi-automatic construction of taxonomies over the Web. We address the problem of discovering high-quality resources that belong in a particular node of a taxonomy....
Building low-diameter p2p networks (2001)
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal
In a peer-to-peer (P2P) network, nodes connect into an existing network and participate in providing and availing of services. There is no dichotomy between a central server and distributed clients....
Random walks with "back buttons". Annals of Applied Probability (2001)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
y We introduce backoff processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the "back button. " With...
On the value of private information (2001)
Christos H. Papadimitriou, Prabhakar Raghavan
Abstract As individuals increasingly take advantage of on-line services, the value of the private information they possess emerges as a problem of fundamental concern. We believe that the principle...
Auditing Boolean Attributes (2000)
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
We study the problem of auditing databases which support statistical sum queries to protect the security of sensitive information; we focus on the special case in which the sensitive information is...
Query Strategies for Priced Information (Extended Abstract) (2000)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Random Walks with "Back Buttons" (2000)
Ronald Fagin, Anna R. Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, ...
We introduce backoff processes, an idealized stochastic model of browsing on the world-wide web, which incorporates both hyperlink traversals and use of the "back button." With some...
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew S. Tomkins, Eli Upfal
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow...
Query Strategies for Priced Information (2000)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, Amit Sahai
We consider a class of problems in which an algorithm seeks to compute a function f over a set of n inputs, where each input has an associated price. The algorithm queries inputs sequentially, trying...
Mining the Link Structure of the World Wide Web (1999)
Soumen Chakrabarti, Byron E. Dom, David Gibson, Jon Kleinberg, Ravi Kumar, Prabhakar Raghavan, ...
Abstract The World Wide Web contains an enormous amount of information, but it can be exceedingly difficult for users to locate resources that are both high in quality and relevant to their...
Mining the Link Structure of the World Wide Web (1999)
Soumen Chakrabarti, Byron E. Dom, David Gibson, Jon Kleinberg, Ravi Kumar, Prabhakar Raghavan, ...
The World Wide Web contains an enormous amount of information, but it can be exceedingly di#cult for users to locate resources that are both high in quality and relevant to their information needs....
The Web as a graph: measurements, models, and methods (1999)
Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew S. Tomkins
. The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a...
Extracting large-scale knowledge bases from the web (1999)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
The subject of this paper is the creation of knowledge bases by enumerating and organizing all web occurrences of certain subgraphs. We focus on subgraphs that are signatures of web phenomena such as...
Extracting Large-Scale Knowledge Bases From the Web (1999)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
The subject of this paper is the creation of knowledge bases by enumerating and organizing all web occurrences of certain subgraphs. We focus on subgraphs that are signatures of web phenomena such as...
On targeting Markov segments (1999)
Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
Consider two user populations, of which one is targeted and the other is not. Users in the targeted population follow a Markov chain on a space of n states. The untargeted population follows another...
The Web as a graph: measurements, models, and methods (1999)
Jon Kleinberg Ravi, Prabhakar Raghavan, Andrew S. Tomkins
. The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a...
Extracting Large-Scale Knowledge Bases From the Web (1999)
Ravi Kumar Prabhakar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
The subject of this paper is the creation of knowledge bases by enumerating and organizing all web occurrences of certain subgraphs. We focus on subgraphs that are signatures of web phenomena such as...
Extracting Large-Scale Knowledge Bases From the Web (1999)
Ravi Kumar Prabhakar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
bases by enumerating and organizing all web occurrences of certain subgraphs. We focus on subgraphs that are signatures of web phenomena such as tightly-focused topic communities, webrings, taxonomy...
On targeting Markov segments (1999)
Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
Consider two user populations, of which one is targeted and the other is not. Users in the targeted population follow a Markov chain P on a space of n states. The untargeted population follows Q,...
Trawling the Web for Emerging Cyber-Communities (1999)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
: The web harbors a large number of communities -- groups of content-creators sharing a common interest -- each of which manifests itself as a set of interlinked web pages. Newgroups and commercial...
Mining the Link Structure of the World Wide Web (1999)
Soumen Chakrabarti, Byron E. Dom, David Gibson, Jon Kleinberg, Ravi Kumar, Prabhakar Raghavan, ...
The World Wide Web contains an enormous amount of information, but it can be exceedingly difficult for users to locate resources that are both high in quality and relevant to their information needs....
Trawling the Web for Emerging Cyber-Communities (1999)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
: The web harbors a large number of communities - groups of content-creators sharing a common interest which manifests itself as a set of web pages. Whereas newgroups and commercial web directories...
Mining the Link Structure of the World Wide Web (1999)
Soumen Chakrabarti Byron, Byron E. Dom, David Gibson, Jon Kleinberg, Ravi Kumar, Prabhakar Raghavan, ...
The World Wide Web contains an enormous amount of information, but it can be exceedingly di#cult for users to locate resources that are both high in quality and relevant to their information needs....
Latent semantic indexing: A probabilistic analysis (1998)
Christos H. Papadimitriou, Prabhakar Raghavan, Santosh Vempala X
Hisao Tamaki z Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without...
Automatic subspace clustering of high dimensional data for data mining applications (1998)
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, Prabhakar Raghavan
Data mining applications place special requirements on clustering algorithms including: the ability to nd clusters embedded in subspaces of high dimensional data, scalability, end-user...
Dynamic Schemes for Speculative Execution of Code (1998)
Prabhakar Raghavan, Hadas Shachnai, Mira Yaniv
Speculative execution of code is becoming a key technique for enhancing the performance of pipeline processors. We study schemes that predict the execution path of a program based on the history of...
Soumen Chakrabarti, Byron Dom, Rakesh Agrawal, Prabhakar Raghavan
We explore how to organize large text databases hierarchically by topic to aid better searching, browsing and filtering. Many corpora, such as internet directories, digital libraries, and patent...
Approximation Algorithms for Segmentation Problems (Extended Abstract) (1998)
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
for STOC 1998) Jon Kleinberg Christos Papadimitriou Prabhakar Raghavan November 14, 1997 Abstract We introduce and study a novel genre of optimization problems, which we call segmentation problems,...
Approximation schemes for euclidean k-medians and related problems (1998)
Sanjeev Arora, Prabhakar Raghavan, Satish Rao
In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points...
A Microeconomic View of Data Mining (1998)
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
We present a rigorous framework, based on optimization, for evaluating data mining operations such as associations and clustering, in terms of their utility in decisionmaking. This framework leads...
Approximation schemes for Euclidean (1998)
Medians And Related, Sanjeev Arora, Prabhakar Raghavan, Satish Rao
In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points...
Recommendation Systems: A Probabilistic Analysis (1998)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
A recommendation system tracks past actions of a group of users to make recommendations to individual members of the group. The growth of computer-mediated marketing and commerce has led to increased...
Gh Av An, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
We introduce and study a novel genre of optimization problems, which we call segmentation problems. Our motivation, in part, is the development of a framework for evaluating certain data mining and...
Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications (1998)
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, Prabhakar Raghavan
Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user...
Clustering Categorical Data: An Approach Based on Dynamical Systems (1998)
David Gibson, Jon Kleinberg, Prabhakar Raghavan
We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data. By "categorical data," we mean tables with fields that...
Spectral Filtering for Resource Discovery (1998)
Soumen Chakrabarti, Byron E. Dom, David Gibson, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins
We develop a technique we call spectral filtering, for discovering high-quality topical resources in hyperlinked corpora. Through relevance and quality judgements collected from 37 users, we show...
Inferring Web Communities from Link Topology (1998)
David Gibson, Jon Kleinberg, Prabhakar Raghavan
The World Wide Web grows through a decentralized, almost anarchic process, and this has resulted in a large hyperlinked corpus without the kind of logical organization that can be built into more...
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
We introduce and study a novel genre of optimization problems, which we call segmentation problems. Our motivation, in part, is the development of a framework for evaluating certain data mining and...
Latent Semantic Indexing: A Probabilistic Analysis (1998)
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, S. Vempala, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Latent Semantic Indexing: A Probabilistic Analysis (1998)
Christos Papadimitriou Computer, Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Inferring Web Communities from Link Topology (1998)
David Gibson, Jon Kleinberg, Prabhakar Raghavan
The World Wide Web grows through a decentralized, almost anarchic process, and this has resulted in a large hyperlinked corpus without the kind of logical organization that can be built into more...
Adversarial Queueing Theory (1998)
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
this paper a request is a path specifying the route followed by a packet. We say that the adversary injects a set of packets when it generates a set of requested paths. We restrict ourselves to the...
Automatic Resource list Compilation by Analyzing Hyperlink Structure and Associated Text (1998)
S. Chakrabarti, B. Dom, Soumen Chakrabarti, Byron Dom, P. Raghavan, And S. Rajagopalan, ...
We describe the design, prototyping and evaluation of ARC, a system for automatically compiling a list of authoritative web resources on any (sufficiently broad) topic. The goal of ARC is to compile...
Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan
this paper. Like almost all such problems, it is NP-hard, even in the unit-weight case formulated above. One can define a segmentation problem (and in fact one of several variants) for every...
Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text (1998)
Soumen Chakrabarti Byron, Byron Dom, Prabhakar Raghavan, Sridhar Rajagopalan, David Gibson, Jon Kleinberg
We describe the design, prototyping and evaluation of ARC, a system for automatically compiling a list of authoritative web resources on any (sufficiently broad) topic. The goal of ARC is to compile...
A Microeconomic View of Data Mining (1998)
Jon Kleinberg Christos, Christos Papadimitriou, Prabhakar Raghavan
We present a rigorous framework, based on optimization, for evaluating data mining operations such as associations and clustering, in terms of their utility in decisionmaking.
Computing on data streams (1998)
Monika Rauch Henzinger, Prabhakar Raghavan
In this paper we study the space requirement of algorithms that make only one (or a small number of) pass(es) over the input data. We study such algorithms under a model of data streams that we...
Automatic subspace clustering of high dimensional data for data mining applications (1998)
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, Prabhakar Raghavan
Data mining applications place special requirements on clustering algorithms including: the ability to nd clusters embedded in subspaces of high dimensional data, scalability, end-user...
Computing on data streams (1998)
Monika Rauch Henzinger, Prabhakar Raghavan
In this paper we study the space requirement of algorithms that make only one (or a small number of) pass(es) over the input data. We study such algorithms under a model of data streams that we...
Web Search Using Automatic Classification (1997)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
Web Search Using Automatic Classification (1997)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
Nonholonomic path planning for pushing a disk among obstacles (1997)
Pankaj K. Agarwal, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan
We consider the path-planning problem for a robot pushing an object in an environment containing ob-stacles. This new variant of the classical robot path-planning problem has several interesting...
A random sampling scheme for path planning (1997)
Jarsme Barraqu, Lydia Kavraki T, Rajeev Motwani T, Prabhakar Raghavan, Tsai-yen Li
Several randomizod path planners have been proposed during the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empirically observed...
Latent Semantic Indexing: A Probabilistic Analysis (1997)
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Constrained TSP and Low-Power Computing (1997)
Moses Charikar, Rajeev Motwani, Prabhakar Raghavan
. In the precedence-constrainedtraveling salesmanproblem (PTSP) we are givena partial order on n nodes, each of which is labeled by one of k points in a metric space.We are to find a visit order...
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata (1997)
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
We investigate time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff's "Jumping Automata for Graphs"....
Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases (1997)
Soumen Chakrabarti, Byron Dom, Rakesh Agrawal, Prabhakar Raghavan
We explore how to organize a text database hierarchically to aid better searching and browsing. We propose to exploit the natural hierarchy of topics, or taxonomy, that many corpora, such as internet...
Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases (1997)
Soumen Chakrabarti Byron, Byron Dom, Rakesh Agrawal, Prabhakar Raghavan
We explore how to organize a text database hierarchically to aid better searching and browsing. We propose to exploit the natural hierarchy of topics, or taxonomy, that many corpora, such as internet...
Nonholonomic Path Planning for Pushing a Disk Among Obstacles (1997)
Pankaj Agarwal, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan
We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot pathplanning problem has several interesting...
Locality-Preserving Hashing in Multidimensional Spaces (1997)
Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, S. Vempala, Santosh Vempala
this paper was published in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 618--625, 1997
Nonholonomic Path Planning for Pushing a Disk Among Obstacles (1997)
Pankaj Agarwal, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan
We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot pathplanning problem has several interesting...
Nonholonomic Path Planning for Pushing a Disk Among Obstacles (1997)
Pankaj Agarwal, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan
We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot pathplanning problem has several interesting...
Locality-Preserving Hashing in Multidimensional Spaces (1997)
Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala
We consider locality-preserving hashing --- in which adjacent points in the domain are mapped to adjacent or nearlyadjacent points in the range --- when the domain is a d- dimensional cube. This...
Constrained TSP and Low-Power Computing (1997)
Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, Craig Silverstein
. In the precedence-constrainedtraveling salesmanproblem (PTSP) we are givena partial order on n nodes, each of which is labeled by one of k points in a metric space.We are to find a visit order...
A random sampling scheme for path planning (1997)
Jérôme Barraqu, Rajeev Motwani, Prabhakar Raghavan
Several randomized path planners have been proposed during the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empirically observed...
A Linear Method for Deviation Detection in Large Databases (1996)
Andreas Arning, Rakesh Agrawal, Prabhakar Raghavan
We describe the problem of finding deviations in large data bases. Normally, explicit information outside the data, like integrity constraints or predefined patterns, is used for deviation detection....
Web Search Using Automatic Classification (1996)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
: We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
A Random Sampling Scheme for Path Planning (1996)
Erome Barraquand Lydia, Lydia Kavraki, Jean-claude Latombe, Tsai-yen Li, Rajeev Motwani, Prabhakar Raghavan
Several randomized path planners have been proposed during the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empirically observed...
Web Search Using Automatic Classification (1996)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
: We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
A Random Sampling Scheme for Path Planning (1996)
Jérôme Barraquand, Lydia Kavraki, Jean-claude Latombe, Tsai-Yen Li, Rajeev Motwani, Prabhakar Raghavan
Several randomized path planners have been proposed during the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empirically observed...
Adversarial Queueing Theory (1996)
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, David P. Williamson
ing with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to 1997 requires prior specific permission and/or a fee. Request permissionserm Publications...
Randomized Query Processing in Robot Path Planning (1996)
Lydia E. Kavraki, Jean-claude Latombe, Rajeev Motwani, Prabhakar Raghavan
The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general...
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height (1995)
Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, Eli Upfal
The random simplex algorithm for linear programming proceeds as follows: at each step, it moves from a vertex v of the polytope to a randomly chosen neighbor of v, the random choice being made from...
The Robot Localization Problem (1995)
Leonidas J. Guibas, Rajeev Motwani, Prabhakar Raghavan
We consider the following problem: given a simple polygon P and a star-shaped polygon V , find a point (or the set of points) in P from which the portion of P that is visible is translation-congruent...
Adversarial Queueing Theory (1995)
Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queueing aimed at addressing some of the restrictions inherent in probabilistic...
On the minimum latency problem (1994)
Blum, Avrim, Chalasani, Prasad, Coppersmith, Don, Pulleyblank, Bill, Raghavan, Prabhakar, Sudan, Madhu
We are given a set of points $p_1,\ldots , p_n$ and a symmetric distance matrix $(d_{ij})$ giving the distance between $p_i$ and $p_j$. We wish to construct a tour that minimizes $\sum_{i=1}^n...
The Minimum Latency Problem (1994)
Avrim Blum, Prasad Chalasani, Bill Pulleyblank, Prabhakar Raghavan
We are given a set of points p 1 ; . . . ; p n and a symmetric distance matrix (d ij ) giving the distance between p i and p j . We wish to construct a tour that minimizes P n i=1 `(i), where `(i) is...
How much can hardware help routing? (Extended Abstract) (1994)
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
Allan Borodin Prabhakar Raghavan y Baruch Schieber y Eli Upfal z April 21, 1994 Abstract We study the extent to which complex hardware can speed up routing. Specifically, we consider the following...
Online Performance-Improvement Algorithms (1994)
Prasad Chalasani August, Prabhakar Raghavan
The results presented in this thesis contribute to two areas of computer science: machine learning and on-line algorithms. One limitation of current theoretical approaches to learning is that most of...
Efficient Routing in All-Optical Networks (1994)
Communication in all-optical networks requires novel routing paradigms. The high bandwidth of the optic fiber is utilized through wavelengthdivision multiplexing: A single physical optical link can...
Motion Planning on a Graph (1994)
Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...
Efficient Routing in All-Optical Networks (1994)
Communication in all-optical networks requires novel routing paradigms. The high bandwidth of the optic fiber is utilized through wavelengthdivision multiplexing: a single physical optical link can...
The Minimum Latency Problem (1994)
Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, Madhu Sudan
We are given a set of points p 1 ; : : : ; p n and a symmetric distance matrix (d ij ) giving the distance between p i and p j . We wish to construct a tour that minimizes P n i=1 `(i), where `(i) is...
A Theory of Wormhole Routing in Parallel Computers (1993)
Sergio Felperin, Prabhakar Raghavan, Eli Upfal
Virtually all theoretical work on message routing in parallel computers has dwelt on packet routing: messages are conveyed as packets, an entire packet can reside at a node of the network, and a...
Time-Space Tradeoffs for Undirected Graph Traversal (1993)
Paul Beame, Paul Beame, Allan Borodin, Allan Borodin, Prabhakar Raghavan, Prabhakar Raghavan, ...
We prove time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff 's "Jumping Automata for Graphs". Our...
Competitive Paging With Locality of Reference (1991)
Allan Borodin, Prabhakar Raghavan, Sandy Irani, Baruch Schieber
Abstract The Sleator-Tarjan competitive analysis of paging [Comm. of the ACM; 28:202- 208, 1985] gives us the ability to make strong theoretical statements about the performance of paging algorithms...
Navigating in Unfamiliar Geometric Terrain (1991)
Avrim Blum, Prabhakar Raghavan, Baruch Schieber, Pii S
Abstract. Consider a robot that has to travel from a start location s to a target t in an environment with opaque obstacles that lie in its way. The robot always knows its current absolute position...
Trading Space for Time in Undirected s-t Connectivity (1991)
Andrei Z. Broder, Prabhakar Raghavan, Robert W. Taylor, Anna R. Karlin, Anna R. Karlin, Eli Upfal, ...
Aleliunas et al. [1] posed the following question: "The reachability problem for undirected graphs can be solved in logspace and O.mn/ time [m is the number of edges and n is the number of...
Time-space tradeoffs for undirected graph traversal (1990)
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
We prove time-space tradeoffs for traversing undi-rected graphs. One of these is a quadratic lower bound on a deterministic model that closely matches the recent probabilistic upper bound of Broder,...
Random walks on weighted graphs and applications to on-line algorithms (1990)
Peter Doyle, Prabhakar Raghavan, Marc Snir
We study the design and analysis of randomized on-line algorithms. We show that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges. 1
Time-space tradeoffs for undirected graph traversal (1990)
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
Abstract. We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff’s “jumping automata for graphs.”
Time-space tradeoffs for undirected graph traversal (1990)
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
We investigate time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff's ``Jumping Automata for Graphs.' '...
The Electrical Resistance Of A Graph Captures Its Commute And Cover Times (1989)
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari
. View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in...
Trading space for time in undirected s-t connectivity (1989)
Andrei Z. Broder, Anna R. Karlin, Anna R. Karlin, Prabhakar Raghavan, Prabhakar Raghavan, ...
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Trading space for time in undirected s-t connectivity (1989)
Andrei Z. Broder, Anna R. Karlin, Anna R. Karlin, Prabhakar Raghavan, Prabhakar Raghavan, ...
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Testing the Model By Multivariate Analysis (1986)
John Philip Keeves, David Gibson, Jon Kleinberg, Prabhakar Raghavan
We describe a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data. By "categorical data," we mean tables with fields that...
Geographic routing in social networks
Liben-Nowell, David, Novak, Jasmine, Kumar, Ravi, Raghavan, Prabhakar, Tomkins, Andrew
We live in a “small world,” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively...
Geographic routing in social networks
Liben-Nowell, David, Novak, Jasmine, Kumar, Ravi, Raghavan, Prabhakar, Tomkins, Andrew
We live in a “small world,” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively...
Stochastic Contention Resolution With Short Delays
We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the...
Stochastic Contention Resolution With Short Delays
Prabhakar Raghavan And, Prabhakar Raghavan, Eli Upfal
We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the...