Relaxation in Text Search using Taxonomies (2009)
Marcus Fontoura, Vanja Josifovski, Ravi Kumar, Christopher Olston, Andrew Tomkins, Sergei Vassilvitskii
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result...
Vanity Fair: Privacy in Querylog Bundles (2009)
Rosie Jones, Ravi Kumar, Bo Pang, Andrew Tomkins
A recently proposed approach to address privacy concerns in storing web search querylogs is bundling logs of multiple users together. In this work we investigate privacy leaks that are possible even...
Microscopic Evolution of Social Networks Jure Leskovec ∗ (2009)
Lars Backstrom, Ravi Kumar, Andrew Tomkins
We present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. For the first time at such a large scale,...
Relaxation in Text Search using Taxonomies (2009)
Marcus Fontoura, Vanja Josifovski, Ravi Kumar, Christopher Olston, Andrew Tomkins, Sergei Vassilvitskii
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result...
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...
Pig Latin: A Not-So-Foreign Language for Data Processing (2008)
Christopher Olston, Benjamin Reed, Utkarsh Srivastava, Ravi Kumar, Andrew Tomkins
There is a growing need for ad-hoc analysis of extremely large data sets, especially at internet companies where innovation critically depends on being able to analyze terabytes of data collected...
Pig Latin: A Not-So-Foreign Language for Data Processing (2008)
Christopher Olston, Benjamin Reed, Utkarsh Srivastava, Ravi Kumar, Andrew Tomkins
There is a growing need for ad-hoc analysis of extremely large data sets, especially at internet companies where innovation critically depends on being able to analyze terabytes of data collected...
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...
ABSTRACT Fast Discovery of Connection Subgraphs (2008)
Christos Faloutsos, Kevin S. Mccurley, Andrew Tomkins
We define a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes. The primary motivation for this work is to provide a paradigm for...
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...
Core Algorithms in the CLEVER System RAVI KUMAR and PRABHAKAR RAGHAVAN (2008)
This article describes the CLEVER search system developed at the IBM Almaden Research Center. We present a detailed and unified exposition of the various algorithmic components that make up the...
STRUCTURE AND EVOLUTION OF (2008)
A critical look at more than one million bloggers and the individual entries of some 25,000 blogs reveals blogger demographics, friendships, and activity patterns over time. Blogs constitute a...
ABSTRACT Structure and Evolution of Online Social Networks (2008)
Ravi Kumar, Jasmine Novak, Andrew Tomkins
In this paper, we consider the evolution of structure within large online social networks. We present a series of measurements of two such networks, together comprising in excess of five million...
ABSTRACT Estimating Corpus Size via Queries (2008)
Andrei Broder, Marcus Fontura, Vanja Josifovski, Ravi Kumar, Rajeev Motwani, Shubha Nabar, ...
We consider the problem of estimating the size of a collection of documents using only a standard query interface. Our main idea is to construct an unbiased and low-variance estimator that can...
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...
Daniel Gruhl, David Liben-nowell, R. Guha, Andrew Tomkins
We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model...
ELSEVIER Abstract Trawling the Web for emerging cyber-communities (2008)
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...
ABSTRACT The Predictive Power of Online Chatter (2008)
Daniel Gruhl, Jasmine Novak, R. Guha, Andrew Tomkins
An increasing fraction of the global discourse is migrating online in the form of blogs, bulletin boards, web pages, wikis, editorials, and a dizzying array of new collaborative technologies. The...
ABSTRACT Evolutionary Clustering (2008)
Deepayan Chakrabarti, Ravi Kumar, Andrew Tomkins
We consider the problem of clustering data over time. An evolutionary clustering should simultaneously optimize two potentially conflicting criteria: first, the clustering at any point in time should...
Ravi Kumar, Jasmine Novak, Bo Pang, Andrew Tomkins
In this paper we study the privacy preservation properties of a specific technique for query log anonymization: tokenbased hashing. In this approach, each query is tokenized, and then a secure hash...
ABSTRACT Anchor-based Proximity Measures (2008)
Amruta Joshi, Ravi Kumar, Benjamin Reed, Andrew Tomkins
We present a family of measures of proximity of an arbitrary node in a directed graph to a pre-specified subset of nodes, called the anchor. Our measures are based on three different propagation...
WWW 2007 / Track: Search Session: Crawlers ABSTRACT The Discoverability of the Web (2008)
Anirban Dasgupta, Arpita Ghosh, Ravi Kumar, Christopher Olston, Sandeep Pandey, Andrew Tomkins
Previous studies have highlighted the high arrival rate of new content on the web. We study the extent to which this new content can be efficiently discovered by a crawler. Our study has two parts....
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....
ABSTRACT n Multi-Structural Databases (2008)
Ronald Fagin, R. Guha, Ravi Kumar, Jasmine Novak, D. Sivakumar, Andrew Tomkins
We introduce the Multi-Structural Database, a new data framework to support efficient analysis of large, complex data sets. An instance of the model consists of a set of data objects, together with a...
“I Know What You Did Last Summer ” — Query Logs and User Privacy ABSTRACT (2008)
Rosie Jones, Ravi Kumar, Bo Pang, Andrew Tomkins
We investigate the subtle cues to user identity that may be exploited in attacks on the privacy of users in web search query logs. We study the application of simple classifiers to map a sequence of...
ABSTRACT Fast Discovery of Connection Subgraphs (2008)
Christos Faloutsos, Kevin S. Mccurley, Andrew Tomkins
We define a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes. The primary motivation for this work is to provide a paradigm for...
Microscopic Evolution of Social Networks (2008)
Leskovec, Jure, Backstrom, Lars, Kumar, Ravi, Tomkins, Andrew
We present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. For the first time at such a large scale,...
Microscopic Evolution of Social Networks (2008)
Leskovec, Jure, Backstrom, Lars, Kumar, Ravi, Tomkins, Andrew
We present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. For the first time at such a large scale,...
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...
of this writing, these companies include Hewlett-Packard Laboratories, Symbios Logic (2007)
Andrew Tomkins, R. Hugo, Patterson Garth Gibson
conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of any supporting organization or the...
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...
ABSTRACT PageRank Computation and the Structure of the Web: Experiments and Algorithms (2007)
Arvind Arasu, Jasmine Novak, Andrew Tomkins, John Tomlin
We describe some computational experiments carried out with variants of the “PageRank ” model due to Page et al., with particular reference to the small and large scale structure of the Web.
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...
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...
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...
The Discoverability of the Web (2007)
Anirban Dasgupta, Arpita Ghosh, Ravi Kumar, Christopher Olston, Sandeep Pandey, Andrew Tomkins
Previous studies have highlighted the high arrival rate of new content on the web. We study the extent to which this new content can be efficiently discovered by a crawler. Our study has two parts....
Enhanced Classification through Exploitation of Hierarchical Structures (2007)
Kunal Vinod, Kumar Punera, Joydeep Ghosh Supervisor, Ross Baldick, Sarfraz Khurshid, Raymond Mooney, ...
Dedicated to my parents, Cdr. Vinod Punera and Shashi Punera.
Barriers for HIV testing during pregnancy in Southern Brazil (2006)
Rosa,Humberto, Goldani,Marcelo Zubaran, Scanlon,Thomas, Silva,Antônio Augusto Moura Da, Giugliani,Elsa Justo, Agranonik,Marilyn, ...
OBJECTIVE: To assess HIV testing rate and determine risk factors for not have been tested during pregnancy. METHODS: A cross-sectional study was carried out in Porto Alegre, Southern Brazil, from...
Navigating Low-Dimensional and Hierarchical Population Networks (2006)
Ravi Kumar, David Liben-nowell, Andrew Tomkins
Abstract. Social networks are navigable small worlds, in which two arbitrary people are likely connected by a short path of intermediate friends that can be found by a “decentralized ” routing...
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...
Disambiguation of references to individuals (2005)
Levon Lloyd, Varun Bhagwan, Daniel Gruhl, Andrew Tomkins, Levon Lloyd
LIMITED DISTRIBUTION NOTICE: This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. Ithas been issued as a Research Report for...
The Volume and Evolution of Web Page Templates (2005)
David Gibson, Kunal Punera, Andrew Tomkins
Web pages contain a combination of unique content and template material, which is present across multiple pages and used primarily for formatting, navigation, and branding. We study the nature,...
Discovering Large Dense Subgraphs in Massive Graphs (2005)
David Gibson Ravi, Ravi Kumar, Andrew Tomkins
We present a new algorithm for finding large, dense subgraphs in massive graphs. Our algorithm is based on a recursive application of fingerprinting via shingles, and is extremely e#cient, capable of...
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...
Maternal Overweight/Obesity and Birthweight of Newborn Babies (2005)
Rondó, Patricia Helen De Carvalho, Tomkins, Andrew
Maternal Overweight/Obesity and Birthweight of Newborn Babies (2005)
Rondó, Patricia Helen De Carvalho, Tomkins, Andrew
Maternal Overweight/Obesity and Birthweight of Newborn Babies (2005)
Rondó, Patricia Helen De Carvalho, Tomkins, Andrew
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...
Sic Transit Gloria Telae:∗ Towards an Understanding of the Web’s Decay (2004)
Bar-Yossef, Ziv, Kumar, Ravi, Broder, Andrei Z, Tomkins, Andrew
The rapid growth of the web has been noted and tracked extensively. Recent studies have however documented the dual phenomenon: web pages have small half lives, and thus the web exhibits rapid death...
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...
Sic transit gloria telae: towards an understanding of the web’s decay (2004)
Ziv Bar-yossef, Ravi Kumar, Andrei Z. Broder, Andrew Tomkins
The rapid growth of the web has been noted and tracked extensively. Recent studies have however documented the dual phenomenon: web pages have small half lives, and thus the web exhibits rapid death...
Sic transit gloria telae: towards an understanding of the web’s decay (2004)
Ziv Bar-yossef, Ravi Kumar, Andrei Z. Broder, Andrew Tomkins
The rapid growth of the web has been noted and tracked extensively. Recent studies have however documented the dual phenomenon: web pages have small half lives, and thus the web exhibits rapid death...
Sic transit gloria telae: towards an understanding of the web’s decay (2004)
Ziv Bar-yossef, Ravi Kumar, Andrei Z. Broder, Andrew Tomkins
The rapid growth of the web has been noted and tracked extensively. Recent studies have however documented the dual phenomenon: web pages have small half lives, and thus the web exhibits rapid death...
Voluntary HIV counseling and testing during prenatal care in Brazil (2003)
Goldani,Marcelo Zubaran, Giugliani,Elsa Regina Justo, Scanlon,Thomas, Rosa,Humberto, Castilhos,Kelli, Feldens,Letícia, ...
OBJECTIVE: Voluntary HIV counseling and testing are provided to all Brazilian pregnant women with the purpose of reducing mother-to-child HIV transmission. The purpose of the study was to assess...
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...
SemTag and Seeker: Bootstrapping the semantic web via automated semantic annotation (2003)
Dill, Stephen, Eiron, Nadav, Gibson, David, Gruhl, Daniel, Guha, Ramanathan, Jhingran, Anant, ...
This paper describes Seeker, a platform for large-scale text analytics, and SemTag, an application written on the platform to perform automated semantic tagging of large corpora. We apply SemTag to a...
SemTag and Seeker: Bootstrapping the semantic web via automated semantic annotation (2003)
Stephen Dill, Nadav Eiron, David Gibson, Daniel Gruhl, R. Guha, Anant Jhingran, ...
This paper describes Seeker, a platform for large-scale text analytics, and SemTag, an application written on the platform to perform automated semantic tagging of large corpora. We apply SemTag to a...
A Case for Automated Large Scale Semantic Annotations (2003)
Stephen Dill, Nadav Eiron, David Gibson, Daniel Gruhl, R. Guha, Anant Jhingran, ...
This paper describes Seeker, a platform for large-scale text analytics, and SemTag, an application written on the platform to perform automated semantic tagging of large corpora. We apply SemTag to a...
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...
Infant mortality rates according to socioeconomic status in a Brazilian city (2001)
Goldani,Marcelo Zubaran, Barbieri,Marco Antonio, Bettiol,Heloisa, Barbieri,Marisa Ramos, Tomkins,Andrew
OBJECTIVE: Data from municipal databases can be used to plan interventions aimed at reducing inequities in health care. The objective of the study was to determine the distribution of infant...
Self-similarity in the web (2001)
Stephen Dill, Ravi Kumar, Kevin S. Mccurley, D. Sivakumar, Andrew Tomkins
Algorithmic tools for searching and mining the Web are becoming increasingly sophisticated and vital. In this context, algorithms that use and exploit structural information about the Web perform...
Self-similarity in the web (2001)
Stephen Dill, Stephen Dill, Ravi Kumar, Ravi Kumar, Ravi Kumar, Kevin Mccurley, ...
Algorithmic tools for searching and mining the web are becoming increasingly sophisticated and vital. In this context, algorithms which use and exploit structural information about the web perform...
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...
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....
Goldani,Marcelo Zubaran, Bettiol,Heloisa, Barbieri,Marco Antonio, Tomkins,Andrew
This study focused on changes in demographic, social, and health-care patterns and pregnancy outcome related to maternal age from 1978-79 to 1994 in Ribeirão Preto, São Paulo State, Brazil....
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...
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....
Minimizing wirelength in zero and bounded skew clock trees (1999)
Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by...
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...
Minimizing Wirelength in Zero and Bounded Skew Clock Trees (1999)
Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronouselements in a VLSI circuit such that the clock arrives at all elements simultaneously. The clock signal is distributed...
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...
Minimizing Wirelength in Zero and Bounded Skew Clock Trees (1999)
Moses Charikar Jon, Jon Kleinberg, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by...
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,...
Minimizing Wirelength in Zero and Bounded Skew Clock Trees (1999)
Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by...
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....
Competitive Analysis of Call Admission Algorithms that Allow Delay. (1998)
Feldmann, Anja, Maggs, Bruce, Sgall, Jiri, Sleator, Daniel D., Tomkins, Andrew
This paper presents an analysis of several simple on-line algorithms for processing requests for connections in distributed networks. These algorithms are called call admission algorithms. Each...
Practical and Theoretical Issues in Prebriefing and Caching (1998)
This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed prefetching and caching in which an application provides information about its...
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...
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...
A Trace-Driven Comparison of Algorithms for Multi-Process Prefetching and Caching. (1997)
Tomkins, Andrew, Patterson, R. H., Gibson, Garth
Recently two groups of researchers have proposed systems that exploit application knowledge to improve I/O performance. Both systems use application knowledge to prefetch data thereby masking I/O...
Practical and theoretical in prefetching and caching / (1997)
Abstract: "This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed prefetching and caching in which an application provides information...
Practical and Theoretical Issues in Prebriefing and Caching. (1997)
Tomkins, Andrew., Carnegie-mellon Univ Pittsburgh Pa Dept Of Computer Science.
This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed prefetching and caching in which an application provides information about its...
A polylog(n)-competitive algorithm for metrical task systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) against an oblivious adversary, on any metric space. This is the first...
Practical and Theoretical Issues in Prefetching and Caching (1997)
This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed prefetching and caching in which an application provides information about its...
Polylog(n)-Competitive Algorithm for Metrical Task Systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) against an oblivious adversary, on any metric space. This is the first...
Polylog(n)-Competitive Algorithm For Metrical Task Systems (1997)
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
We present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of O(log 6 n) for arbitrary metric spaces, against an oblivious adversary. This is the...
Block Edit Models for Approximate String Matching (1997)
Daniel Lopresti, Andrew Tomkins
In this paper we examine string block edit distance, in which two strings A and B are compared by extracting collections of substrings and placing them into correspondence. This model accounts for...
Informed Multi-Process Prefetching and Caching (1997)
Andrew Tomkins, R. Hugo Patterson, Garth Gibson
Informed prefetching and caching based on application disclosure of future I/O accesses (hints) can dramatically reduce the execution time of I/O-intensive applications. A recent study showed that,...
Temporal-Domain Matching of Hand-Drawn Pictorial Queries (1997)
Daniel Lopresti, Andrew Tomkins
In this chapter we discuss the problem of searching a database of hand-drawn documents for a particular hand-drawn query. We show how to break the problem into two parts. First, a matching algorithm...
Practical and Theoretical Issues in Prefetching and Caching (1997)
Submitted inpartial ful llment of the requirements for the degree ofDoctor of Philosophy. Thesis Committee:
Block edit models for approximate string matching (1997)
Daniel Lopresti, Andrew Tomkins
In this paper we examine string block edit distance, in which two strings A and B are compared by extracting collections of substrings and placing them into correspondence. This model accounts for...
A trace-driven comparison of algorithms for parallel prefetching and caching (1996)
Kai Li, Tracy Kimbrel, Tracy Kimbrel, Andrew Tomkins, Andrew Tomkins, R. Hugo Patterson, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A trace-driven comparison of algorithms for parallel prefetching and caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo, Patterson Brian, Bershad Pei Cao
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel Andrew, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
1 High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
Avrim Blum, Merrick L. Furst, Andrew Tomkins
We consider an extension of the standard on-line model to settings in which an on-line algorithm has free time between successive requests in an input sequence. During this free time, the algorithm...
A Trace-Driven Comparison of Algorithms for Multi-Process Prefetching and Caching (1996)
Andrew Tomkins, R. Hugo Patterson, R. Hugo, Garth Gibson
Recently two groups of researchers have proposed systems that exploit application knowledge to improve I/O performance. Both systems use application knowledge to prefetch data thereby masking I/O...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Felten, ...
High-performance I/O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in isolation, even though...
A trace-driven comparison of algorithms for parallel prefetching and caching (1996)
Tracy Kimbrel, Andrew Tomkins, R. Hugo, Patterson Brian, Bershad Pei Cao
High�performance I�O systems depend on prefetching and caching in order to deliver good performance to applications. These two techniques have generally been considered in iso� lation � even...
Validation of Image Defect Models for Optical Character Recognition (1995)
Yanhong Li, Daniel Lopresti, George Nagy, Andrew Tomkins
In this paper, we consider the problem of evaluating character image generators that model distortions encountered in optical character recognition (OCR). While a number of such defect models have...
Computing in the Ink Domain (Extended Abstract) (1995)
Daniel Lopresti, Andrew Tomkins
) Daniel Lopresti Andrew Tomkins dpl@research.panasonic.com andrewt@cs.cmu.edu Matsushita Information Technology Laboratory Panasonic Technologies, Inc. Two Research Way Princeton, NJ 08540 USA...
Temporal-Domain Matching of Hand-Drawn Pictorial Queries (1995)
Daniel Lopresti And, Daniel Lopresti, Andrew Tomkins
1 as well. Existing string matching algorithms are not flexible enough to capture these kinds of block motion. Time B1 B2 B3 B4 B5 B6 B7 B3 B4 B5 B7 B7 B7 B3 B4 B6 B5 B1 B2 B2 Picture A Basic Blocks...
Lower Bounds for Two Call Control Problems (1995)
We present lower bounds for two call control scheduling problems. For the problem of scheduling infinite-duration calls deterministically without pre-emption on a linear array of processors, in which...
Competitive Analysis of Call Admission Algorithms that Allow Delay (1995)
Anja Feldmann, Bruce Maggs, Jiri Sgall, Daniel D. Sleator, Andrew Tomkins
This paper presents an analysis of several on-line algorithms, called call admission algorithms, for processing requests for connections in distributed networks. Each request comes with a source, a...
Determinants of Nutritional Status in South-west Uganda (1995)
Vella, Venanzio, Tomkins, Andrew, Nviku, John, Marshall, Tom
In a cross-sectional survey carried out of 4320 children 0–59 months old in South-west Uganda various socio-economic and environmental factors were related to poor nutritional status. Diarrhoea...
Roy, S.K., Tomkins, Andrew, Tait, Susan Fairweather, Mahalanabis, Dilip, Akramuzzaman, S.M., Dewan, Nahrina
Roy, S.K., Tomkins, Andrew, Tait, Susan Fairweather, Mahalanabis, Dilip, Akramuzzaman, S.M., Dewan, Nahrina
Systematic Bias in OCR Experiments (1994)
Yuhlin Chang, Daniel P. Lopresti, Andrew Tomkins, Jeffrey Zhou, Jiangying Zhou
In this paper, we present the results from large-scale OCR experiments simulating several different groups of researchers performing the same test, but using slightly different equipment and...
Online Interval Scheduling (1994)
Richard J. Lipton, Andrew Tomkins
We introduce the online interval scheduling problem, in which a set of intervals of the positive real line is presented to a scheduling algorithm in order of start time. Upon seeing each interval,...
Determinants of Stunting and Recovery from Stunting in Northwest Uganda (1994)
VELLA, VENANZIO, TOMKINS, ANDREW, BORGESI, ARMANDO, MIGLIORI, GIOVANNI BATTISTA, ORYEM, VINCENT YOOMAN
BackgroundSocioeconomic deprivation is associated with unhealthy living conditions and insufficient nutrient intake which affect linear growth. This study investigates the major risk factors which...
Approximate Matching of Hand-Drawn Pictograms (1993)
Daniel P. Lopresti, Andrew Tomkins
We describe a new naming paradigm for pen-based computing which we call Pictographic Naming. Using our approach, traditional character-by-character handwriting recognition (HWX) is avoided. Instead,...
Daniel P. Lopresti, Andrew Tomkins
We describe pictographic naming,a new approach to naming for pen-based computers, in which filenames are pictures rather than ASCII strings. Handwriting recognition (HWX) of a name is delayed as long...
Approximate matching of hand-drawn pictograms (1993)
Daniel P. Lopresti, Andrew Tomkins
We describe a new naming paradigm for pen-based computing which we call Pictographic Naming. Using our approach, traditional character-by-character handwriting recognition (HWX) is avoided. Instead,...
A Computational Model of Teaching (1992)
Jeffrey Jackson, Andrew Tomkins
Goldman and Kearns [GK91] recently introduced a notionof the teaching dimensionof a concept class. The teaching dimension is intended to capture the combinatorial difficulty of teaching a concept...
Awwal, A.M.M. Anisul, Wahed, M.A., Anwar, Udoy S., Jahangir, Md., Heywood, Peter, Tomkins, Andrew, ...
Khanum, Sultana, Garelick, Hemda, Nasir, Uddin, Mann, George, Tomkins, Andrew
The serological response to measles vaccine was tested in Bangladesh in groups of infants aged 4-6 months who received equal doses of Edmonston-Zagreb or Schwarz vaccine by subcutaneous injection or...
Thesis (Ph.D.)--University of Canterbury, 1984.
Street children in Latin America
Scanlon, Thomas J, Tomkins, Andrew, Lynch, Margaret A, Scanlon, Francesca
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...
Hesketh, Therese, Ding, Qu Jian, Tomkins, Andrew
Objectives. To inform a prevention strategy, this study determined the prevalence of and attitudes toward smoking among Chinese secondary school students.
Street children in Latin America
Scanlon, Thomas J, Tomkins, Andrew, Lynch, Margaret A, Scanlon, Francesca
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...
Hesketh, Therese, Ding, Qu Jian, Tomkins, Andrew
Objectives. To inform a prevention strategy, this study determined the prevalence of and attitudes toward smoking among Chinese secondary school students.
Luabeya, Kany-Kany Angelique, Mpontshane, Nontobeko, Mackay, Malanie, Ward, Honorine, Elson, Inga, Chhagan, Meera, ...
On the Searchability of Electronic Ink
Daniel Lopresti, Andrew Tomkins
Pen-based computers and personal digital assistant's (PDA's) are new technologies that are growing in importance. In previous papers, we have espoused a philosophy we call "Computing...
Block Edit Models for Approximate String Matching
Daniel Lopresti Andrew, Andrew Tomkins
In this paper we examine the concept of string block edit distance, where two strings A and B are compared by extracting collections of substrings and placing them into correspondence. This model...