Discovering Links between Lexical and Surface Features in Questions and Answers (2009)
Information retrieval systems, based on keyword match, are evolving to question answering systems that return short passages or direct answers to questions, rather than URLs pointing to whole pages....
Modeling the Benefits of Mixed Data and Task Parallelism (2008)
Soumen Chakrabarti, James Demmel, Katherine Yelick
Mixed task and data parallelism exists naturally in many applications, but utilizing it may require sophisticated scheduling algorithms and software support. Recently, significant research effort has...
Abstract Accelerated Focused Crawling through Online Relevance Feedback ∗ (2008)
Soumen Chakrabarti, Kunal Punera, Mallela Subramanyam
The organization of HTML into a tag tree structure, which is rendered by browsers as roughly rectangular regions with embedded text and HREF links, greatly helps surfers locate and click on links...
Learning Random Walks to Rank Nodes in Graphs (2008)
Π Qπ, Π Qπ, Alekh Agarwal, Soumen Chakrabarti
• Typically studied in vector spaces • Graphs model relationships naturally
Resource scheduling for parallel database and scientific applications
1 Introduction Automatic Web Resource Discovery (2008)
Classical information retrieval (IR) is concerned with indexing a collection of documents and answering
User Interaction in the BANKS System: A Demonstration (2008)
B. Aditya, Soumen Chakrabarti, Rushi Desai, Arvind Hulgeri, Hrishikesh Karambelkar, Rupesh Nasre Parag, ...
The BANKS system supports keyword search on databases storing structured/semi-structured data. Answers to keyword queries are ranked, and as in IR systems, the top answers may not be exactly what a...
Abstract Enhanced hypertext categorization using hyperlinks (2008)
A major challenge in indexing unstructured hypertext data-bases is to automatically extract meta-data that enables structured search using topic taxonomies, circumvents key-word ambiguity, and...
Extractors and taggers turn unstructured text into entityrelation (ER) graphs where nodes are entities (email, paper, person, conference, company) and edges are relations (wrote, cited, works-for)....
We introduce a new, powerful class of text proximity queries: find an instance of a given “answer type ” (person, place, distance) near “selector ” tokens matching given literals or...
Alan Frieze, Juan Vera, Soumen Chakrabarti
influence of search engines on preferential attachment
Shantanu Godbole, Abhay Harpale, Sunita Sarawagi, Soumen Chakrabarti
Abstract. We present the HIClass (Hyper Interactive text Classification) system, an interactive text classification system which combines the cognitive power of humans with the power of automated...
Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher Z, Lars Rasmussen X
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds (log n = log log n) balls with high probability. Recently, Azar et al. analyzed...
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...
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 Accelerated Focused Crawling through Online Relevance Feedback ∗ (2007)
Soumen Chakrabarti, Kunal Punera, Mallela Subramanyam
The organization of HTML into a tag tree structure, which is rendered by browsers as roughly rectangular regions with embedded text and HREF links, greatly helps surfers locate and click on links...
Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, S. Sudarshan
With the growth of the Web, there has been a rapid increase in the number of users who need to access online databases without having a detailed knowledge of the schema or of query languages; even...
Announcements and Notices (2007)
Kaushik Chakrabarti, Michael Ortega, Kriengkrai Porkaew, Sharad Mehrotra, Leejay Wu, Christos Faloutsos, ...
TCDE Election Notice and Position Statement.................................................... 50 TCDE Election Ballot.................................................................... back cover...
X Flair, Soumen Chakrabarti, A. U. Thor
In this report we prove that (n 1 + n 2 + \Delta \Delta \Delta + nm)!
Mining the Web First Edition Errata (2007)
Soumen Chakrabarti, Gordon Paynter, Horst Rothmeier, Marcin Sydow, Dries Van Dyck
Page 2, second line from bottom, space missing: “humanity,and”. Page 6, line 12: hyphen missing in “nonobvious ” — should be “non-obvious”.
Learning random walks to rank nodes in graphs (2007)
Alekh Agarwal, Soumen Chakrabarti
Ranking nodes in graphs is of much recent interest. Edges, via the graph Laplacian, are used to encourage local smoothness of node scores in SVM-like formulations with generalization guarantees. In...
Learning random walks to rank nodes in graphs (2007)
Alekh Agarwal, Soumen Chakrabarti
Ranking nodes in graphs is of much recent interest. Edges, via the graph Laplacian, are used to encourage local smoothness of node scores in SVM-like formulations with generalization guarantees. In...
Learning parameters in entity relationship graphs from ranking preferences (2006)
Soumen Chakrabarti, Alekh Agarwal
Abstract. Semi-structured entity-relation (ER) data graphs have diverse node and edge types representing entities (paper, person, company) and relations (wrote, works for). In addition, nodes contain...
Learning parameters in entity relationship graphs from ranking preferences (2006)
Soumen Chakrabarti, Alekh Agarwal
Abstract. Semi-structured entity-relation (ER) data graphs have diverse node and edge types representing entities (paper, person, company) and relations (wrote, works for). In addition, nodes contain...
Dr. Sunita Sarawagi, Dr. Soumen Chakrabarti
Inter-class relationships in text classification
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results (2005)
Pandey, Sandeep, Roy, Sourashis, Olston, Christopher, Cho, Junghoo, Chakrabarti, Soumen
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Enhanced Answer Type Inference from Questions using Sequential Models (2005)
Vijay Krishnan, Sujatha Das, Soumen Chakrabarti
Question classification is an important step in factual question answering (QA) and other dialog systems. Several attempts have been made to apply statistical machine learning approaches, including...
Enhanced Answer Type Inference from Questions using Sequential Models (2005)
Vijay Krishnan, Sujatha Das, Soumen Chakrabarti
Question classification is an important step in factual question answering (QA) and other dialog systems. Several attempts have been made to apply statistical machine learning approaches, including...
Shuffling a stacked deck: the case for partially randomized ranking of search engine results (2005)
Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results (2005)
Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results (2005)
Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Bidirectional Expansion For Keyword Search On Graph Databases (2005)
Varun Kacholia, Shashank Pandit, Soumen Chakrabarti, S. Sundarshan, Rushi Desai, Hrishikesh Karambelkar
Relational, XML and HTML data can be represented as graphs with entities as nodes and relationships as edges. Text is associated with nodes and possibly edges. Keyword search on such graphs has...
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results (2005)
Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results (2005)
Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Shuffling a Stacked Deck: The Case for Partially (2005)
Randomized Ranking Of, Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Shuffling a stacked deck: the case for partially randomized ranking of search engine results (2005)
Sandeep Pandey, Sourashis Roy, Christopher Olston, Junghoo Cho, Soumen Chakrabarti
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is...
Is Question Answering an Acquired Skill? (2004)
Ramakrishnan, Ganesh, Chakrabarti, Soumen, Paranjpe, Deepa, Bhattacharyya, Pushpak
We present a question answering (QA) system which learns how to detect and rank answer passages by analyzing questions and their answers (QA pairs) provided as training data. We built our system in...
Breaking through the syntax barrier: Searching with entities and relations (2004)
Abstract. The next wave in search technology will be driven by the identification, extraction, and exploitation of real-world entities represented in unstructured textual sources. Search systems will...
Is Question Answering an Acquired Skill? (2004)
Ganesh Ramakrishnan, Soumen Chakrabarti, Deepa Paranjpe, Pushpak Bhattacharya
We present a question answering (QA) system which learns how to detect and rank answer passages by analyzing questions and their answers (QA pairs) provided as training data. We built our system in...
Document classification through interactive supervision of document and term labels (2004)
Shantanu Godbole, Abhay Harpale, Sunita Sarawagi, Soumen Chakrabarti
Abstract. Effective incorporation of human expertise, while exerting a low cognitive load, is a critical aspect of real-life text classification applications that is not adequately addressed by...
Monitoring the Dynamic Web to respond to Continuous Queries (2003)
Pandey, Sandeep, Ramamritham, Krithi, Chakrabarti, Soumen
Continuous queries are queries for which responses given to users must be continuously updated, as the sources of interest get updated. Such queries occur, for instance, during on-line decision...
Question Answering via Bayesian Inference on Lexical Relations (2003)
Ganesh Ramakrishnan, Apurva Jadhav, Ashutosh Joshi, Soumen Chakrabarti, Pushpak Bhattacharyya
Many researchers have used lexical networks and ontologies to mitigate synonymy and polysemy problems in Question Answering (QA), systems coupled with taggers, query classifiers, and answer...
The structure of broad topics on the Web (2002)
Chakrabarti, Soumen, Joshi, Mukul M., Punera, Kunal, Pennock, David M.
The Web graph is a giant social network whose properties have been measured and modeled extensively in recent years. Most such studies concentrate on the graph structure alone, and do not consider...
Accelerated Focused Crawling through Online Relevance Feedback (2002)
Chakrabarti, Soumen, Punera, Kunal, Subramanyam, Mallela
The organization of HTML into a tag tree structure, which is rendered by browsers as roughly rectangular regions with embedded text and HREF links, greatly helps surfers locate and click on links...
The Structure of Broad Topics on the Web (2002)
Chakrabarti, Soumen, Joshi, Mukul M., Punera, Kunal, Pennock, David M.
The Web graph is a giant social network whose properties have been measured and modeled extensively in recent years. Most such studies concentrate on the graph structure alone, and do not consider...
Keyword searching and browsing in databases using BANKS (2002)
Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, S. Sudarshan
With the growth of the Web, there has been a rapid increase in the number of users who need to access online databases without having a detailed knowledge of the schema or of query languages; even...
Fast and accurate text classification via multiple linear discriminant projections (2002)
Soumen Chakrabarti, Shourya Roy, Mahesh V. Soundalgekar
Abstract. Support vector machines (SVMs) have shown superb performance for text classification tasks.They are accurate, robust, and quick to apply to test instances.Their only potential drawback is...
Banks: Browsing and keyword searching in relational databases (2002)
B. Aditya, Gaurav Bhalotia, Soumen Chakrabarti, Arvind Hulgeri, Charuta Nakhe, Parag S. Sudarshan
The BANKS system enables keyword-based search on databases, together with data and schema browsing. BANKS enables users to extract information in a simple manner without any knowledge of the schema...
The structure of broad topics on the web (2002)
Soumen Chakrabarti, Mukul M. Joshi, Kunal Punera, David M. Pennock
The Web graph is a giant social network whose properties have been measured and modeled extensively in recent years. Most such studies concentrate on the graph structure alone, and do not consider...
Banks: Browsing and keyword searching in relational databases (2002)
B. Aditya, Gaurav Bhalotia, Soumen Chakrabarti, Arvind Hulgeri, Charuta Nakhe, Parag S. Sudarshan
The BANKS system enables keyword-based search on databases, together with data and schema browsing. BANKS enables users to extract information in a simple manner without any knowledge of the schema...
Topic distillation is the process of finding authoritative Web pages and comprehensive ``hubs'' which reciprocally endorse each other and are relevant to a given query. Hyperlink-based topic...
Keyword search in databases (2001)
Arvind Hulgeri, Gaurav Bhalotia, Charuta Nakhe, Soumen Chakrabarti, S. Sudarshan
Querying using keywords is easily the most widely used form of querying today. While keyword searching is widely used to search documents on the Web, querying of databases currently relies on complex...
Data mining for hypertext: A tutorial survey (2000)
With over 800 million pages covering most areas of human endeavor, the World-wide Web is a fertile ground for data mining research to make a difference to the effectiveness of information search....
Mining Themes From Bookmarks (2000)
Soumen Chakrabarti, Yusuf Batterywala
Many Web surfers maintain bookmark files containing URLs organized into folders which represent topics by function or content. We propose a new framework for discovering themes among such folders...
Memex: A browsing assistant for (2000)
Collaborative Archiving And, Soumen Chakrabarti, Sandeep Srivastava, Mallela Subramanyam, Mitul Tiwari
Keyword indices, topic directories, and link-based rankings are used to search and structure the rapidly growing Web today. Surprisingly little use is made of years of browsing experience of millions...
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....
Distributed hypertext resource discovery through examples (1999)
We describe the architecture of a hypertext resource discovery system using a relational database. Such a system can answer questions that combine page contents, metadata, and hyperlink structure in...
Distributed Hypertext Resource Discovery Through Examples (1999)
Soumen Chakrabarti, Byron E. Dom
We describe the architecture of a hypertext resource discovery system using a relational database. Such a system can answer questions that combine page contents, metadata, and hyperlink structure in...
Focused crawling: a new approach to topic-specific Web resource discovery (1999)
The rapid growth of the World-Wide Web poses unprecedented scaling challenges for general-purpose crawlers and search engines. In this paper we describe a new hypertext resource discovery system...
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....
Focused crawling: a new approach to topic-specific web resource discovery (1999)
The rapid growth of the world-wide web poses unprecedented scaling challenges for general-purpose crawlers and search engines. In this paper we describe a new hypertext information management system...
Surfing the Web Backwards (1999)
Soumen Chakrabarti, David A. Gibson, Kevin S. Mccurley
From a user’s perspective, hypertext links on the web form a directed graph between distinct information sources. We investigate the effects of discovering “backlinks ” from web resources,...
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...
Mining Surprising Patterns Using Temporal Description Length (1998)
Soumen Chakrabarti Sunita, Soumen Chakrabarti, Sunita Sarawagi, Byron Dom
We propose a new notion of surprising temporal patterns in market basket data, and algorithms to find such patterns. This is distinct from finding frequent patterns as addressed in the common mining...
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...
Flow and Stretch Metrics for Scheduling Continuous Job Streams (1998)
Michael Bender, Soumen Chakrabarti, S. Muthukrishnan
this paper, we isolate and study the problem of scheduling a continuous stream of requests of varying sizes. More precisely, assume a request or job j has
Enhanced Hypertext Categorization Using Hyperlinks (1998)
Soumen Chakrabarti, Byron Dom, And Piotr Indyk, Piotr Indyk
A major challenge in indexing unstructured hypertext databases is to automatically extract meta-data that enables structured search using topic taxonomies, circumvents keyword ambiguity, and improves...
Mining Surprising Patterns Using Temporal Description Length (1998)
Soumen Chakrabarti, Sunita Sarawagi, Byron Dom
We propose a new notion of surprising temporal patterns in market basket data, and algorithms to find such patterns. This is distinct from finding frequent patterns as addressed in the common mining...
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...
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...
Efficient resource scheduling in multiprocessors /--by Soumen Chakrabarti. (1996)
Thesis (Ph. D. in Computer Science)--University of California, Berkeley, December 1996.
Improved scheduling algorithms for minsum criteria (1996)
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
Abstract. We consider the problem of finding near-optimal solutions for a variety of NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work...
Global Communication Analysis and Optimization (1996)
Soumen Chakrabarti, Manish Gupta, Jong-deok Choi
Reducing communication cost is crucial to achieving good performance on scalable parallel machines. This paper presents a new compiler algorithm for global analysis and optimization of communication...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Exte Nd Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Extend Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
Resource Scheduling for Parallel Database and Scientific Applications (1996)
Soumen Chakrabarti, S. Muthukrishnan
We initiate a study of resource scheduling problems in parallel database and scientific applications. Based on this study we formulate a problem. In our formulation, jobs specify their running times...
Resource Scheduling for Parallel Database and Scientific Applications (1996)
Soumen Chakrabarti, S. Muthukrishnan
We initiate a study of resource scheduling problems in parallel database and scientific applications. Based on this study we formulate a problem. In our formulation, jobs specify their running times...
Efficient Resource Scheduling in Multiprocessors (1996)
As multiprocessing becomes increasingly successful in scientific and commercial computing, parallel systems will be subjected to increasingly complex and challenging workloads. To ensure good job...
Improved Scheduling Algorithms for Minsum Criteria (Extended Abstract) (1996)
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of finding near-optimal solutions for a variety of NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work has led...
Portable Parallel Irregular Applications (1995)
Katherine Yelick, Chih-po Wen, Soumen Chakrabarti, Etienne Deprit, Jeff Jones, Arvind Krishnamurthy
Software developers for distributed memory multiprocessors often complain about the lack of libraries and tools for developing and performance tuning their applications. While some tools exist for...
Multipol: A Distributed Data Structure Library (1995)
Soumen Chakrabarti, Etienne Deprit, Eun-jin Im, Jeff Jones, Arvind Krishnamurthy, Chih-po Wen, ...
Applications with dynamic data structures, unpredictable computational costs, and irregular data access patterns require substantial effort to parallelize. Much of their programming complexity comes...
Parallel Randomized Load Balancing (1995)
Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al....
Modeling the Benefits of Mixed Data and Task Parallelism (1995)
Soumen Chakrabarti, James Demmel, Katherine Yelick
Mixed task and data parallelism exists naturally in many applications, but utilizing it may require sophisticated scheduling algorithms and software support. Recently, significant research effort has...
Runtime Support For Portable Distributed Data Structures (1995)
Chih-po Wen, Soumen Chakrabarti, Etienne Deprit, Arvind Krishnamurthy, Katherine Yelick
Multipol is a library of distributed data structures designed for irregular applications, including those with asynchronous communication patterns. In this paper, we describe the Multipol runtime...
Modeling the Benefits of Mixed Data and Task Parallelism (1995)
Soumen Chakrabarti, James Demmel, Katherine Yelick
Mixed task and data parallelism exists naturally in many applications, but utilizing it may require sophisticated scheduling algorithms and software support. Recently, significant research effort has...
Parallel Data Structures for Symbolic Computation (1995)
Katherine Yelick, Soumen Chakrabarti, Etienne Deprit, Jeff Jones, Arvind Krishnamurthy, Chih-po Wen
Symbolic applications often require dynamic irregular data structures, such as linked lists, unbalanced trees, and graphs, and they exhibit unpredictable computational patterns that lead to...
Parallel Randomized Load Balancing (1995)
Preliminary Version, Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds \Theta(log n= log log n) balls with high probability. Recently, Azar et al....
Parallel Randomized Load Balancing (1995)
Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds #(log n/ log log n) balls with high probability. More recently, Azar et al....
Parallel randomized load balancing (1995)
Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen
It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds Θ(log n / log log n) balls with high probability. More recently, Azar et al....
Parallel randomized load balancing (1995)
Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, Lars Rasmussen
ABSTRACT: It is well known that after placing n balls independently and uniformly at random into n bins, the fullest bin holds �Ž log n�log log n. balls with high probability. More recently,...
Randomized Load Balancing for Tree-structured Computation (1994)
Soumen Chakrabarti, Abhiram Ranade, Katherine Yelick
In this paper, we study the performance of a randomized algorithm for balancing load across a multiprocessor executing a dynamic irregular task tree. Specifically, we show that the time taken to...
Distributed data structures and algorithms for Gröbner basis computation (1994)
Soumen Chakrabarti, Katherine Yelick
We present the design and implementation of a parallel algorithm for computing Gröbner bases on distributed memory multiprocessors. The parallel algorithm is irregular both in space and time: the...
Data Structures for Irregular Applications (1993)
Katherine A. Yelick, Soumen Chakrabarti, Etienne Deprit, Jeff Jones, Arvind Krishnamurthy, Chih-po Wen
Parallelization of any large application can be a difficult task, but when the application contains irregular patterns of communication and control, the parallelization effort is higher and the...
On the Correctness of a Distributed Memory Gröbner Basis Algorithm (1993)
Soumen Chakrabarti, Katherine Yelick
. We present an asynchronous MIMD algorithm for Grobner basis computation. The algorithm is based on the well-known sequential algorithm of Buchberger. Two factors make the correctness of our...
Implementing an Irregular Application on a Distributed Memory Multiprocessor (1993)
Soumen Chakrabarti, Katherine Yelick
Parallelism with irregular patterns of data, communication and computation is hard to manage efficiently. In this paper we present a case study of the Gröbner basis problem, a symbolic algebra...
On the Correctness of a Distributed Memory Gröbner Basis Algorithm (1992)
Soumen Chakrabarti, Katherine Yelick
We present an asynchronous MIMD algorithm for Grobner basis computation. The algorithm is based on the well-known sequential algorithm of Buchberger. Two factors make the correctness of our algorithm...