Quasi-Proportional Mechanisms: Prior-free Revenue Maximization (2009)
Mirrokni, Vahab, Muthukrishnan, S., Nadav, Uri
Inspired by Internet ad auction applications, we study the problem of allocating a single item via an auction when bidders place very different values on the item. We formulate this as the problem of...
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan
Abstract. Many data analysis applications deal with large matrices and involve approximating the matrix using a small number of “components. ” Typically, these components are linear combinations...
Sponsored Search Auctions with Markovian Users (2009)
Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, Martin Pál
Abstract. Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. The most popular auction for sponsored...
Online Stochastic Matching: Beating 1-1/e (2009)
Feldman, Jon, Mehta, Aranyak, Mirrokni, Vahab, Muthukrishnan, S.
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani...
Via Embeddings, Graham Cormode, S. Muthukrishnan
Abstract. If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal rearrangements in the form of deletions, block moves, inversions etc. to...
Graham Cormode, S. Muthukrishnan
The edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes and changes needed to convert R to S. Given a text string t of length n, and a pattern...
Abstract Counting Twig Matches in a Tree (2009)
Zhiyuan Chen, S. Muthukrishnan, H. V. Jagadish
We describe efficient algorithms for accurately estimating the number of matches of a small node-labeled tree, i.e., a twig, in a large node-labeled tree, using a summary data structure. This problem...
Graham Cormode, S. Muthukrishnan
Many network flows between (source, dest) pairs Want a snapshot at time t of the flows This defines a (massive) vector, and we ask: Summarise the current state How does state at time t compare with...
Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the...
Optimal Cache-Aware Suffix Selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[ildots N]$, $1 leq i leq N$. We study the suffix...
How to Increase the Acceptance Ratios of Top Conferences? (2008)
Graham Cormode, Artur Czumaj, S. Muthukrishnan
In the beginning was the pub. This work was triggered by a pub conversation where the authors observed that many resumés list acceptance ratios of conferences where their papers appear 4, boasting...
MoDB: Database System For Synthesizing Human Motion (2008)
Timothy Edmunds, S. Muthukrishnan, Subarna Sadhukhan, Shinjiro Sueda
Enacting and capturing real motion for all potential scenarios is prohibitively expensive; hence, there is a great demand to synthetically generate realistic human motion. However, it is a central...
In Proceedings of ICDE ’05 1131 MoDB: Database System For Synthesizing Human Motion (2008)
Timothy Edmunds, S. Muthukrishnan, Subarna Sadhukhan, Shinjiro Sueda
Enacting and capturing real motion for all potential scenarios is prohibitively expensive; hence, there is a great demand to synthetically generate realistic human motion. However, it is a central...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
Permutation Editing and Matching (2008)
Via Embeddings, Graham Cormode, S. Muthukrishnan
3 EECS, Case Western Reserve University, Cleveland, OH; cenk@cwru.edu Abstract. If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova
Abstract. We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as...
Graham Cormode, S. Muthukrishnan
What is clustering? We have a bunch of items... we want to discover the clusters... Types of clustering What is the quantity we are trying to optimize? Two types of clustering K-centers Pick k points...
A Truthful Mechanism for Offline Ad Slot Scheduling (2008)
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál
Abstract. We consider the Offline Ad Slot Scheduling problem, where advertisers must be scheduled to sponsored search slots during a given period of time. Advertisers specify a budget constraint, as...
On Distributing Symmetric Streaming Computations (2008)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein
A common approach for dealing with large data sets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive data sets, however, even making a...
Periodicity Testing with Sublinear Samples and Space (2008)
Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp
Abstract In this work, we are interested in finding representative trends in long large data streamsin the presence of computational constraints; to this end we present algorithms for discovering...
Har-Peled, Sariel, Muthukrishnan, S.
We study a generalization of the classical median finding problem to batched query case: given an array of unsorted $n$ items and $k$ (not necessarily disjoint) intervals in the array, the goal is to...
Gianni Franceschini, S. Muthukrishnan
It is well known that n integers in the range [1, n c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range can be sorted in O(n √ log log n) time...
Permutation Editing and Matching via (2008)
Graham Cormode, S. Muthukrishnan
Abstract. If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal rearrangements in the form of deletions, block moves, inversions etc. to...
Graham Cormode, S. Muthukrishnan, Lower Bounds
– New approaches for this problem and its extensions. Some questions We see a large number of individual transactions (such as Amazon book sales) – What are the top sellers today? We are...
Streaming Algorithms for Data in Motion (2008)
M. Hoffmann, S. Muthukrishnan, Rajeev Raman
Abstract. We propose two new data stream models: the reset model and the delta model, motivated by applications to databases, and to tracking the location of spatial points. We present algorithms for...
DoWitcher: Effective Worm Detection and Containment in the Internet Core (2008)
S. Ranjan, S. Shah, A. Nucci, M. Munafò, R. Cruz, S. Muthukrishnan
Abstract—Enterprise networks are increasingly offloading the responsibility for worm detection and containment to the carrier networks. However, current approaches to the zero-day worm detection...
Abstract Counting Twig Matches in a Tree (2008)
Zhiyuan Chen, S. Muthukrishnan, H. V. Jagadish
We describe efficient algorithms for accurately estimating the number of matches of a small node-labeled tree, i.e., a twig, in a large node-labeled tree, using a summary data structure. This problem...
MoDB: Database System For Synthesizing Human Motion (2008)
Timothy Edmunds, S. Muthukrishnan, Subarna Sadhukhan, Shinjiro Sueda
Enacting and capturing real motion for all potential scenarios is terribly expensive; hence, there is a great demand to synthetically generate realistic human motion. However, it is a central...
ABSTRACT Stochastic Models for Budget Optimization in Search-Based Advertising (2008)
Internet search companies sell advertisement slots based on users ’ search queries via an auction. Advertisers have to solve a complex optimization problem of how to place bids on the keywords of...
Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk
Data mining research typically assumes that the data to be analyzed has been identified, gathered, cleaned, and pro-cessed into a convenient form. While data mining tools greatly enhance the ability...
Bidding to the Top: VCG and Equilibria of (2008)
Position-based Auctions, Gagan Aggarwal, Jon Feldman, S. Muthukrishnan
Abstract. Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount...
1 THE GRAHAM-KNOWLTON PROBLEM REVISITED (2008)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
In late ¢ ¡ ’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest...
© 1997 Springer-Verlag New York Inc. Detecting False Matches in String-Matching Algorithms 1 (2008)
Abstract. Consider a text string of length n, a pattern string of length m, and a match vector of length n which declares each location in the text to be either a mismatch (the pattern does not occur...
The Graham-Knowlton Problem Revisited ⋆ (2008)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
Abstract. In late 60’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the...
SubspaceSamplingandRelative-ErrorMatrix Approximation:Column-BasedMethods (2008)
Michaelw. Mahoney, S. Muthukrishnan
Abstract. Givenan m*n matrix A andaninteger k lessthantherankof A,the"best"rank k approximationto A thatminimizestheerrorwithrespecttotheFrobeniusnormis...
Masaru Kitsuregawa, Betty Salzberg, Gonzalo Navarro, Ricardo Baeza-yates, Erkki Sutinen, Jorma Tarhio, ...
IntegratingDiverseInformationManagementSystems:ABriefSurvey..................................
SubspaceSamplingandRelative-ErrorMatrix Approximation:Column-Row-BasedMethods (2008)
Michaelw. Mahoney, S. Muthukrishnan
Abstract. Muchrecentworkinthetheoreticalcomputerscience,linearalgebra,andmachinelearninghasconsideredmatrixdecompositionsof thefollowingform:givenan m * n matrix A,decomposeitasaproduct...
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
www.cs.rutgers.edu/~muthu How does one deal with massive data sets that is available for analyses? We will describe the classical data stream model in which we make one pass over the data and with...
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan
Abstract. We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: • An upper bound of 3n − 1 in...
Simple Approximation Algorithm for Nonoverlapping Local Alignments (2008)
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan
this paper will show how to implement this algorithm in O(N log N) time
Yossi Matias, S. Muthukrishnan, Jacob Ziv
Abstract. Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role. In this paper, we consider one...
Vineet Bafna, S. Muthukrishnan, R. Ravi
Ribonucleic acid (RNA) strings are strings over the four-letter alphabet fA; C; G;Ug with a secondary structure of base-pairing between A0U and C 0 G pairs in the string 1. Edges are drawn between...
S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes E. Gehrke
We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of...
Paolo Ferragina, S. Muthukrishnan, Mark De Berg
Current object oriented programming languages (OOPLs) rely on mono-method dispatching. Recent research has identified multi-methods as a new, powerful feature to be added to OOPLs, and several...
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Flip Korn AT&T Labs-Research (2007)
Zhiyuan Chen, Nick Koudas, S. Muthukrishnan
In a variety of applications ranging from optimizing queries on alphanumeric attributes to providing approximate counts of documents containing several query terms, there is an increasing need to...
Techniques and Applications for Approximating String Distances -- Rough Draft (April 11 2000) (2007)
Graham Cormode Muthukrishnan, S. Muthukrishnan, Mike Paterson, Suleyman Cenk S
this paper, we introduce techniques which allow us to approximate the distance between strings under a variety of distance measures. The first technique is Hamming Signatures, which computes an O(log...
On the Temporal HZY Compression Scheme (2007)
Cohen Matias Muthukrishnan, Z. Cohen, Y. Matias, S. Muthukrishnan, J. Ziv
08> [(k \Gamma1)fi+1 : kfi] defined to be the number of distinct occurrences of the context T [(k \Gamma 1)fi \Gamma x : (k \Gamma 1)fi] between the leftmost occurrence of T [(k \Gamma 1)fi \Gamma...
Algorithms for FPGA Switch Module Routability Analysis (2007)
Shashidhar Thakur, D. F. Wong, S. Muthukrishnan
We consider a switch module routing problem for symmetric array FPGAs. The work is motivated by two applications. The first is that of efficiently evaluating switch module designs [9]. The second is...
Bhaskar Ghosh, S. Muthukrishnan, Martin Schultz
Consider the following load balancing problem. We are given a graph with arbitrary topology and an arbitrary load distribution on the nodes. In each time step, a node can send any amount of load to...
Layout of the Batcher Bitonic Sorter (2007)
Extend Ed, Shimon Even, S. Muthukrishnan, Michael S. Paterson, Suleyman Cenk S
) Shimon Even S. Muthukrishnan y Michael S. Paterson z Suleyman Cenk S . ahinalp x Abstract The grid-area required by a sorting net for input vectors of length N is shown to be at least (N \Gamma 1)...
Layout of the Batcher Bitonic Sorter (Extended Abstract) (2007)
Shimon Even, S. Muthukrishnan, Michael S. Paterson, Süleyman Cenk Sahinalp, Suleyman Cenk S
The grid-area required by a sorting net for input vectors of length N is shown to be at least (N \Gamma 1) 2 =2. Of all sorting nets which use o(N 2 ) comparators, the bitonic sorting net of Batcher...
Engineering the Compression of Massive Tables: An Experimental Approach SIAM 2000. (2007)
We study the problem of compressing massive tables. We devise a novel compression paradigm—training for lossless compression— which assumes that the data exhibit dependencies that can be learned...
is a linear combination of dictionary (2007)
Anna C. Gilbert, S. Muthukrishnan, Martin J. Strauss, Input A R
One of the central problems of modern mathematical approximation theory is to approximate functions, or signals, concisely, with elements from a large candidate set called a dictionary. Formally, we...
Rohit Ananthakrishna, Abhinandan Das, S. Muthukrishnan, Johannes Gehrke, Divesh Srivastava
In many applications such as IP network management, data arrives in streams, and queries over those streams need to be processed online using limited storage. Correlated-sum (CS) aggregates are a...
Using Õ-grams in a DBMS for Approximate String Processing (2007)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, ...
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data. This is due, for example, to the...
Approximation Algorithms For MAX-MIN Tiling Piotr Berman y (2007)
Bhaskar Dasgupta, S. Muthukrishnan
The MAX-MIN tiling problem is as follows. We are given a two-dimensional array A[1; : : : ; n][1; : : : ; n] where each entry A[i][j] stores a non-negative number. Dene a tile of A to be a subarray...
Shashidhar Thakur, Yao-wen Chang, D. F. Wong, S. Muthukrishnan
We consider a switch-module-routing problem for symmetrical-array FPGAs. This problem was first introduced in [21]. They used it to evaluate the routability properties of switch modules they...
muthuresearch. art. com (2007)
Flipsresearch Art Com, S. Muthukrishnan, Divesh Srivastava
Reverse Nearest Neighbor (RNN) queries have been studied for finite, stored data sets and are of interest for decision support. However, in many applications such as fixed wireless telephony access...
Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan
An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1 m 2 pattern is given. The algorithm takes O(log log m) time and does O(m 1 m 2) work, where m = maxfm...
L. Becchetti, S. Diggavi, S. Leonardi, A. Marchetti-spaccamela, S. Muthukrishnan, T. Nandagopal, ...
Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users...
Graham Cormode, S. Muthukrishnan
Data streams often consist of multiple signals. Consider a stream of multiple signals (i; a i;j) where i's correspond to the domain, j's index the dierent signals and a i;j 0 to the value...
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
On 2-Tuple String Matching (2007)
Paolo Ferragina, Paolo Ferragina, S. Muthukrishnan, S. Muthukrishnan
y 1
A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, M. J. Strauss
Monitoring and analyzing traffic data generated from large ISP networks imposes challenges both at the data gathering phase as well as the data analysis itself. Still both tasks are crucial for...
Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A 3. " We give a sketching algorithm, that constructs a small sketch from the stream of...
Flip Korn AT&T Labs--Research (2007)
Zhiyuan Chen, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Raymond Ng, Divesh Srivastava
We describe efficient algorithms for accurately estimating the number of matches of a small node-labeled tree, i.e., a twig, in a large node-labeled tree, using a summary data structure. This problem...
1 Tradeoffs for Packet Classification (2007)
Anja Feldmann, S. Muthukrishnan
Abstract---We present an algorithmic framework for solving the packet classification problem that allows various access time vs. memory tradeoffs. It reduces the multi-dimensional packet...
How to Increase the Acceptance Ratios of Top Conferences? (2007)
Graham Cormode, Artur Czumaj, S. Muthukrishnan
In the beginning was the pub. This work was triggered by a pub conversation where the authors observed that many resumes list acceptance ratios of conferences where their papers appear, boasting the...
Stochastic models for budget optimization in search-based. manuscript (2007)
S. Muthukrishnan, Martin Pál, Zoya Svitkina
Internet search companies sell advertisement slots based on users ’ search queries via an auction. Advertisers have to determine how to place bids on the keywords of their interest in order to...
Gianni Franceschini, S. Muthukrishnan
It is well known that n integers in the range [1, n c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1, U] can be sorted in O(n √ log log...
In-place suffix sorting (2007)
G. Franceschini, S. Muthukrishnan
Abstract. Given string T = T[1,..., n], the suffix sorting problem is to lexicographically sort the suffixes T[i,..., n] for all i. This problem is central to the construction of suffix arrays and...
Radix sorting with no extra space (2007)
Gianni Franceschini, S. Muthukrishnan
Abstract. It is well known that n integers in the range [1, n c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1, U] can be sorted in O(n √...
Combinatorial Algorithms for Compressed Sensing (2006)
Graham Cormode, S. Muthukrishnan
Abstract. In sparse approximation theory, the fundamental problem is to reconstruct a signal A ∈ R n from linear measurements 〈A, ψi 〉 with respect to a dictionary of ψi’s. Recently, there...
Estimating entropy and entropy norm on data streams (2006)
Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan
Abstract. We consider the problem of computing information theoretic functions such as entropy on a data stream, using sublinear space. Our first result deals with a measure we call the “entropy...
On the complexity of processing massive, unordered, distributed data (2006)
Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, Zoya Svitkina
The popular model for processing massive data sets is the streaming model in which the processor makes a pass over the input with polylog(n)-space. However, with current data sets, even making a...
Compressing and searching xml data via two zips (2006)
P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan
XML is fast becoming the standard format to store, exchange and publish over the web, and is getting embedded in applications. Two challenges in handling XML are its size (the XML representation of a...
Subspace sampling and relative-error matrix approximation: Column-based methods (2006)
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan
Abstract. Given an m×n matrix A and an integer k less than the rank of A, the “best ” rank k approximation to A that minimizes the error with respect to the Frobenius norm is Ak, which is...
Subspace sampling and relative-error matrix approximation: Column-based methods (2006)
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan
Abstract. Much recent work in the theoretical computer science, linear algebra, and machine learning has considered matrix decompositions of the following form: given an m × n matrix A, decompose it...
Estimating entropy and entropy norm on data streams (2006)
Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan
Abstract. We consider the problem of computing information theoretic functions such as entropy on a data stream, using sublinear space. Our first result deals with a measure we call the “entropy...
Workload-Optimal histograms on streams (2005)
S. Muthukrishnan, M. Strauss, X. Zheng
Histograms are used in many ways in conventional databases and in data stream processing for summarizing massive data distributions. Previous work on constructing histograms on data streams with...
Effective computation of biased quantiles over data streams (2005)
Graham Cormode, S. Muthukrishnan
Skew is prevalent in many data sources such as IP traffic streams. To continually summarize the distribution of such data, a high-biased set of quantiles (e.g., 50th, 90th and 99th percentiles) with...
Summarizing and mining inverse distributions on data streams via dynamic inverse sampling (2005)
Graham Cormode, S. Muthukrishnan
Database management systems face the challenge of dealing with massive data distributions which arrive at high speeds while there is only small storage available for managing and mining them....
A heartbeat mechanism and its application in Gigascope (2005)
Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk, Oliver Spatscheck
Data stream management systems often rely on ordering properties of tuple attributes in order to implement non-blocking operators. However, query operators that work with multiple streams, such as...
Summarizing and mining inverse distributions on data streams via dynamic inverse sampling (2005)
Graham Cormode, S. Muthukrishnan
Database management systems face the challenge of dealing with massive data distributions which arrive at high speeds while there is only small storage available for managing and mining them....
Improved time bounds for near-optimal sparse Fourier representation via sampling (2005)
A. C. Gilbert, S. Muthukrishnan, M. Strauss
contact authors for latest revision. We study the problem of finding a Fourier representation R of B terms for a given discrete signal A of length N. The Fast Fourier Transform (FFT) can find the...
A Heartbeat Mechanism and its Application in Gigascope (2005)
Theodore Johnson Muthukrishnan, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk, Oliver Spatscheck
Data stream management systems often rely on ordering properties of tuple attributes in order to implement non-blocking operators. However, query operators that work with multiple streams, such as...
Streams, Security and Scalability (2005)
Theodore Johnson Muthukrishnan, Theodore Johnson, S. Muthukrishnan, Oliver Spatscheck, Divesh Srivastava
Network-based attacks, such as DDoS attacks and worms, are threatening the continued utility of the Internet. As the variety and the sophistication of attacks grow, early detection of potential...
Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling (2005)
Graham Cormode, S. Muthukrishnan, Irina Rozenbaum
Emerging data stream management systems approach the challenge of massive data distributions which arrive at high speeds while there is only small storage by summarizing and mining the distributions...
Effective computation of biased quantiles over data streams (2005)
Graham Cormode, S. Muthukrishnan
Skew is prevalent in many data sources such as IP traffic streams. To continually summarize the distribution of such data, a high-biased set of quantiles (e.g., 50th, 90th and 99th percentiles) with...
Domain-driven data synopses for dynamic quantiles (2005)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Abstract—In this paper, we present new algorithms for dynamically computing quantiles of a relation subject to insert as well as delete operations. At the core of our algorithms lies a small-space...
Efficient string matching algorithms for combinatorial universal denoising (2005)
S. Chen, S. Diggaviý, S. Dusadý, S. Muthukrishnan
Inspired by the combinatorial denoising method DUDE [13], we present efficient algorithms for implementing this idea for arbitrary contexts or for using it within subsequences. We also propose...
Sampling algorithms in a stream operator (2005)
Theodore Johnson, S. Muthukrishnan, Irina Rozenbaum
Complex queries over high speed data streams often need to rely on approximations to keep up with their input. The research community has developed a rich literature on approximate streaming...
Improved range-summable random variable construction algorithms (2005)
A. R. Calderbank, A. Gilbert, K. Levchenko, S. Muthukrishnan, M. Strauss
Approximation Algorithms for Array Partitioning Problems (2005)
S. Muthukrishnan, Muthukrishnan Torsten Suel
We study the problem of optimally partitioning a two-dimensional array of elements by cutting each coordinate axis into (resp., ) intervals, resulting in rectangular regions. This problem arises in...
Effective computation of biased quantiles over data streams (2005)
Graham Cormode, S. Muthukrishnan
Skew is prevalentin many data sourcessuchas IP traffic streams. To continually summarize the distribution of such data, a highbiased set of quantiles (e.g., 50th, 90th and 99th percentiles) with...
Holistic UDAFs at streaming speeds (2004)
Graham Cormode, S. Muthukrishnan
Many algorithms have been proposed to approximate holistic aggregates, such as quantiles and heavy hitters, over data streams. However, little work has been done to explore what techniques are...
An improved data stream summary: The Count-Min sketch and its applications (2004)
Graham Cormode, S. Muthukrishnan
Abstract. We introduce a new sublinear space data structure—the Count-Min Sketch — for summarizing data streams. Our sketch allows fundamental queries in data stream summarization such as point,...
Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data (2004)
Graham Cormode, S. Muthukrishnan
Data items archived in data warehouses or those that arrive online as streams typically have attributes which take values from multiple hierarchies (e.g., time and geographic location; source and...
Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data (2004)
Graham Cormode, S. Muthukrishnan
Data items archived in data warehouses or those that arrive online as streams typically have attributes which take values from multiple hierarchies (e.g., time and geographic location; source and...
What's New: Finding Significant Differences in Network Data Streams (2004)
Graham Cormode, S. Muthukrishnan
Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing...
Holistic UDAFs at Streaming Speeds (2004)
Graham Cormode, Theodore Johnson, Flip Korn, S. Muthukrishnan
Many algorithms have been proposed to approximate holistic aggregates, such as quantiles and heavy hitters, over data streams. However, little work has been done to explore what techniques are...
Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data (2004)
Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava
Data items archived in data warehouses or those that arrive online as streams typically have attributes which take values from multiple hierarchies (e.g., time and geographic location; source and...
The Graham-Knowlton Problem Revisited (2004)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
In late 60’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest trips....
Mining deviants in time series data streams (2004)
One of the central tasks in managing, monitoring and mining data streams is that of identifying outliers. There is a long history of study of various outliers in statistics and databases, and a...
Holistic UDAFs at streaming speeds (2004)
Graham Cormode, S. Muthukrishnan
Many algorithms have been proposed to approximate holistic aggregates, such as quantiles and heavy hitters, over data streams. However, little work has been done to explore what techniques are...
Maintenance of multidimensional histograms (2003)
S. Muthukrishnan, Martin Strauss
1 Introduction Let Aj an N * N dynamic array1 at time j. Input is a series of updates. The jth input is (i, k, cj), which updates Aj-1 to be Aj, where
Comparing sequences with segment rearrangements (2003)
Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp
Abstract. Computational genomics involves comparing sequences based on "similarity " for detecting evolutionary and functional relation-ships. Until very recently, available...
Inferring Tree Topologies Using Flow Tests (2003)
S. Muthukrishnan, Torsten Suel, Radek Vingralek
We consider the problem of discovering the structure of an unknown hierarchical network by means of measuring the maximum flow between the root and selected
What’s hot and what’s not: Tracking most frequent items dynamically (2003)
Graham Cormode, S. Muthukrishnan
Most database management systems maintain statistics on the underlying relation. One of the important statistics is that of the “hot items ” in the relation: those that appear many times (most...
Estimating dominance norms of multiple data streams (2003)
Graham Cormode, S. Muthukrishnan
Abstract. There is much focus in the algorithms and database communities on designing tools to manage and mine data streams. Typically, data streams consist of multiple signals. Formally, a stream of...
Comparing sequences with segment rearrangements (2003)
Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp
Center for Comp. Genomics, CWRU.
One-Pass Wavelet Decompositions of Data Streams (2003)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Data Streams: Algorithms and Applications (2003)
Contents 1 Introduction 2 1.1 Puzzle 1: Finding Missing Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Puzzle 2: Fishing . . . . . . . . . . . . . . . . . . . . . . . . . ....
Approximate String Joins in a Database (Almost) for Free (2003)
Erratum Luis Gravano, Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, ...
case the result returned by the Figure 1 query is incomplete and su#ers from "false negatives," in contrast to our claim to the contrary in [GIJ 01b]. In general, the string pairs that are...
What's Hot and What's Not: Tracking Most Frequent Items Dynamically (2003)
Graham Cormode, S. Muthukrishnan
Most database management systems maintain statistics on the underlying relation. One of the important statistics is that of the "hot items" in the relation: those that appear many times...
Data Streams: Algorithms and Applications (2003)
Contents 1 Introduction 2 1.1 Puzzle 1: Finding Missing Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Puzzle 2: Fishing . . . . . . . . . . . . . . . . . . . . . . . . . ....
Approximation Algorithms for Average Stretch Scheduling (2003)
Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman
We study the basic problem of preemptive scheduling of a stream of jobs on a single processor.
Finding hierarchical heavy hitters in data streams (2003)
Graham Cormode, S. Muthukrishnan, Divesh Srivastava
Aggregation along hierarchies is a critical summary technique in a large variety of online applications including decision support, and network management (e.g., IP clustering, denial-of-service...
Efficient algorithms for document retrieval problems (2002)
Abstract We are given a collection D of text documents d1; : : : ; dk, withP i jdij = n, which may be preprocessed. In the documentlisting problem, we are given an online query comprising of a...
Mining database structure; or, how to build a data quality browser (2002)
Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyukat
ABSTRACT Data mining research typically assumes that the data to be analyzed has been identified, gathered, cleaned, and processed into a convenient form. While data mining tools greatly enhance the...
Comparing data streams using hamming norms (how to zero in (2002)
Graham Cormode, Mayur Datar, Piotr Indyk, S. Muthukrishnan
Abstract—Massive data streams are now fundamental to many data processing applications. For example, Internet routers produce large scale diagnostic data streams. Such streams are rarely stored in...
Near-optimal sparse Fourier representations via sampling (2002)
A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss
We give an algorithm for nding a Fourier representation R ofBterms for a given discrete signal A of lengthN, such thatkA,Rk 2 2 is within the factor (1 +) of best possible kA,Roptk 2 2. Our algorithm...
Comparing data streams using hamming norms (how to zero in (2002)
Graham Cormode, Mayur Datar, S. Muthukrishnan, Piotr Indyk
Massive data streams are now fundamental to many data processing applications. For example, Internet routers produce large scale diagnostic data streams. Such streams are rarely stored in traditional...
Estimating rarity and similarity over data stream windows (2002)
Email:datar@cs.stanford.edu. This work was done while the author was visiting AT&T Research
How to summarize the universe: Dynamic maintenance of quantiles (2002)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Order statistics, i.e., quantiles, are frequently used in databases both at the database server as well as the application level. For example, they are useful in selectivity estimation during query...
Range Searching in Categorical Data: Colored Range Searching on Grid (2002)
Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan
Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and spatial databases. Given a set of geometric objects, a typical range query...
Near-Optimal Sparse Fourier Representations via Sampling (Extended Abstract) (2002)
A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Ka \gamma Roptk
A. C. Gilbert S. Guha P. Indyk S. Muthukrishnan M. Strauss ABSTRACT We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal A of length N , such 2 is within...
Fast, Small-Space Algorithms for Approximate Histogram Maintenance (Extended Abstract) (2002)
Anna Gilbert, Yannis Kotidis, Sudipto Guha, S. Muthukrishnan, Piotr Indyk, Martin J. Strauss
Anna C. Gilbert AT&T Labs---Research agilbert@research.att.com Yannis Kotidis AT&T Labs---Research kotidis@research.att.com Sudipto Guha CIS,University of Pennsylvania sudipto@cis.upenn.edu...
Slice and Dice: A Simple, Improved Approximate Tiling Recipe (2002)
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan
We are given a two dimensional array A[1 \Delta \Delta \Delta n; 1 \Delta \Delta \Delta n] where each A[i; j] stores a non-negative number. A (rectangular) tiling of A is a collection of rectangular...
Fast, Small-Space Algorithms for Approximate Histogram (2002)
Maintenance Extend Ed, Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, ...
Anna C. Gilbert AT&T Labs---Research agilbert@research.att.com Yannis Kotidis AT&T Labs---Research kotidis@research.att.com Sudipto Guha CIS,University of Pennsylvania sudipto@cis.upenn.edu...
How to Summarize the Universe: Dynamic Maintenance of Quantiles (2002)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Order statistics, i.e., quantiles, are frequently used in databases both at the database server as well as the application level. For example, they are useful in selectivity estimation during query...
How to summarize the universe: Dynamic maintenance of quantiles (2002)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Abstract Order statistics, i.e., quantiles, are frequently used in databases both at the database server as well as the application level. For example, they are useful in selectivity estimation...
Improved Algorithms for Stretch Scheduling (2002)
Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman
We study the basic problem of preemptive scheduling of an online stream of jobs on a single processor. The ith job arrives at time r(i) and has processing time p(i) that is known at the time of its...
Mining database structure; or, how to build a data quality browser (2002)
Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk
Near-optimal sparse Fourier representations via sampling (2002)
A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss
We give an algorithm for nding a Fourier representation R ofBterms for a given discrete signal A of lengthN, such thatkA;Rk 2 2 is within the factor (1 +) of best possible kA;Roptk 2 2. Our algorithm...
Optimal and approximate computation of summary statistics for range aggregates (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. Hence, there has been a lot of focus on “selectivity...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Abstract We present techniques for computing small spacerepresentations of massive data streams. These are inspired by traditional wavelet-based approx-imations that consist of specific linear...
Approximate string joins in a database (almost) for free (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
In [GIJ + 01a, GIJ + 01b] we described how to use q-grams in an RDBMS to perform approximate string joins. We also showed how to implement the approximate join using plain SQL queries. Specifically,...
Using q-grams in a DBMS for Approximate String Processing (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, ...
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data. This is due, for example, to the...
Optimal and approximate computation of summary statistics for range aggregates (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. Hence, there has been a lot of focus on "selectivity...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Self-adjusting data structures for external memory string access (2001)
V. Ciriani, V. Ciriani, P. Ferragina, P. Ferragina, F. Luccio, F. Luccio, ...
Data warehouses are increasingly storing and managing large scale string data, and dealing with large volume of transactions that update and search string databases. Motivated by this context, we...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Approximate string joins in a database (almost) for free (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data especially for more complex queries...
Internet packet filter management and rectangle geometry (2001)
We consider rule sets for internet packet routing and filtering, where each rule consists of a range of source addresses, a range of destination addresses, a priority, and an action. A given packet...
Improved Approximation Algorithms for Rectangle Tiling and Packing (Extended Abstract) (2001)
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan, Suneeta Ramaswami
) 1 Introduction We study several rectangle tiling and packing problems. These are natural combinatorial problems that arise in many applications in databases, parallel computing and image...
Using q-grams in a DBMS for Approximate String Processing (2001)
Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Lauri Pietarinen, ...
String data is ubiquitous, and its management has taken on particular importance in the past few years. Approximate queries are very important on string data. This is due, for example, to the...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Improved Approximation Algorithms for Rectangle Tiling and Packing (2001)
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan, Suneeta Ramaswami
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Selectivity estimation for Boolean queries (2000)
Zhiyuan Chen, Nick Koudas, S. Muthukrishnan
In a variety of applications ranging from optimizing queries on alphanumeric attributes to providing approximate counts of documents containing several query terms, there is an increasing need to...
Selectivity estimation for Boolean queries (2000)
Zhiyuan Chen, Nick Koudas, S. Muthukrishnan
In a variety of applications ranging from optimizing queries on alphanumeric attributes to providing approximate counts of documents containing several query terms, there is an increasing need to...
Influence sets based on reverse nearest neighbor queries (2000)
Inherent in the operation of many decision support and continuous referral systems is the notion of the "influence" of a data point on the database. This notion arises in examples...
Optimal Histograms for Hierarchical Range Queries (Extended Abstract) (2000)
Nick Koudas, S. Muthukrishnan, Divesh Srivastava
) Nick Koudas AT&T Labs--Research koudas@research.att.com S. Muthukrishnan AT&T Labs--Research muthu@research.att.com Divesh Srivastava AT&T Labs--Research divesh@research.att.com 1...
Approximate Nearest Neighbors and Sequence Comparison With Block Operations (2000)
S. Muthukrishnan, Suleyman Cenk Sahinalp, Suleyman Cenk S
We study sequence nearest neighbors (SNN). Let D be a database of n sequences; we would like to preprocess D so that given any on-line query sequence Q we can quickly find a sequence S in D for which...
Piotr Berman, Bhaskar Dasgupta, S. Muthukrishnan
) Abstract We show an upper bound of 3n on size of the Binary Space Partitioning (BSP) tree for a set of n isothetic rectangles, and an upper bound of 2n if the rectangles tile the underlying space....
Scalable, Low-Overhead Network Delay Estimation (2000)
Volkan Ozdemir, S. Muthukrishnan, Injong Rhee
The round trip network delay times between pairs of nodes in a multicast session is a key parameter; it is used in suppressing the implosion of request and repair packets, in detecting congestion,...
Scalable, Low-Overhead Network Delay Estimation (2000)
Volkan Ozdemir Muthukrishnan, S. Muthukrishnan, Injong Rhee
Estimating the network delays between each pair of nodes in a multicast session is the key parameter in reliable multicast; it is used, among other things, in suppressing the implosion of request and...
Tradeoffs for Packet Classification (2000)
Anja Feldmann, S. Muthukrishnan
We present an algorithmic framework for solving the packet classification problem that allows various access time vs. memory tradeoffs. It reduces the multidimensional packet classification problem...
Scalable, Low-Overhead Network Delay Estimation (2000)
Volkan Ozdemir, S. Muthukrishnan, Injong Rhee
Estimating the network delays between each pair of nodes in a multicast session is the key parameter in reliable multicast; it is used, among other things, in suppressing the implosion of request and...
Compact Grid Layouts of Multi-Level Networks (1999)
S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel
We consider the problem of generating layouts of multilevel networks, in particular, switching, sorting, and interconnection networks, as compactly as possible on VLSI grids. Besides traditional...
Layered Multicast Recovery (1999)
Injong Rhee, Srinath R. Joshi, Minsuk Lee, S. Muthukrishnan, Volkan Ozdemir
We study the problem of localizing repair packets when packets are lost during multicasts. When repair packets are multicasted, a highly lossy receiver may swamp the entire multicast...
Scalable, Low-Overhead Network Delay Estimation (1999)
Volkan Ozdemir, S. Muthukrishnan, Injong Rhee
Estimating the network delays between each pair of nodes in a multicast session is the key parameter in reliable multicast; it is used, among other things, in suppressing the implosion of request and...
Layered Multicast Recovery (1999)
Injong Rhee, Srinath R. Joshi, Minsuk Lee, S. Muthukrishnan, Volkan Ozdemir
We study the problem of localizing repair packets when packets are lost. When repair packets are multicasted, a highly lossy receiver may swamp the entire multicast "group" with duplicate...
Scheduling to Minimize Average Stretch (1999)
Johannes E. Gehrke, S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen
We consider the classical problem of online preemptive job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the...
Layered Multicast Recovery (1999)
Injong Rhee Srinath, Srinath R. Joshi, Minsuk Lee, S. Muthukrishnan, Volkan Ozdemir
We study the problem of localizing repair packets when packets are lost. When repair packets are multicasted, a highly lossy receiver may swamp the entire multicast "group" with duplicate...
Compact Grid Layouts of Some Multi-Level Networks (1999)
S. Muthukrishnan, Michael S. Paterson, Suleyman Cenk Sahinalp, Torsten Suel
We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible, that is, with minimum area, on VLSI...
Scheduling to Minimize Average Stretch without Migration (1999)
Luca Becchetti, Stefano Leonardi, S. Muthukrishnan
We study the problem of scheduling parallel machines online, allowing preemptions while disallowing migration of jobs that have been scheduled on one machine to another. For a given job, we measure...
TIGHT ANALYSES OF TWO LOCAL LOAD BALANCING ALGORITHMS (1999)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow (1998)
S. Muthukrishnan, Torsten Suel
We study local-control algorithms for maximum flow and multicommodity flow problems in distributed networks. We propose a second-order method for accelerating the convergence of the...
Optimal Histograms with Quality Guarantees (1998)
H. V. Jagadish, Viswanath Poosala, Nick Koudas, Ken Sevcik, S. Muthukrishnan, Torsten Suel
Histograms are commonly used to capture attribute value distribution statistics for query optimizers. More recently, histograms have also been considered as a way to produce quick approximate answers...
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
An Adversarial Model for Distributed Dynamic Load Balancing (1998)
S. Muthukrishnan, Rajmohan Rajaraman
We study the problem of balancing the load on processors of an arbitrary network. If jobs arrive or depart during the process of load balancing, we have the dynamic load balancing problem; otherwise,...
B. Gosh, Bhaskar Ghosh, S. Muthukrishnan, Martin H. Schultz
) Bhaskar Ghosh S. Muthukrishnan y Martin H. Schultz z Informix Software Inc. U. Warwick Yale U. Abstract We consider the following general problem modeling load balancing in a variety of distributed...
Augmenting Suffix Trees, with Applications (1998)
Yossi Matias, S. Muthukrishnan, Süleyman Cenk Sahinalp, Jacob Ziv
. Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role. In this paper, we consider one algorithmic...
Optimal parallel randomized renaming (1997)
Martin Farach, S. Muthukrishnan
We consider the Renaming Problem, a basic processing step in string algorithms, for which we give a simultaneously work and time optimal Las Vegas type PRAM algorithm. The Renaming Problem is closely...
Algorithms for an fpga switch module routing problem with application to global routing (1997)
Shashidhar Thakur, Yao-wen Chang, Associate Member, D. F. Wong, S. Muthukrishnan
Abstract — We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA’s). This problem was first introduced in [21]. They used it to evaluate the...
The architecture of a software library for string processing (1997)
A. Czumaj, P. Ferragina, L. Gasieniec, S. Muthukrishnan, J. L. Träff
We present our project to develop a software library of basic tools and data structures for string processing. Our goal is to provide an environment for testing new algorithms as well as for...
Efficient Array Partitioning (1997)
Sanjeev Khanna Muthukrishnan, S. Muthukrishnan, Steven Skiena
. We consider the problem of partitioning an array of n items into p intervals so that the maximum weight of the intervals is minimized. The currently best known bound for this problem is O(np)...
Efficient Array Partitioning (1997)
Sanjeev Khanna, S. Muthukrishnan, Steven Skiena
. We consider the problem of partitioning an array of n items into p intervals so that the maximum weight of the intervals is minimized. The currently best known bound for this problem is O(n+p 1+ffl...
Richa Agarwala, Serafim Batzoglou, Scott E. Decatur, Sridhar Hannenhalli, Martin Farach, S. Muthukrishnan, ...
We consider the problem of determining the three-dimensional folding of a protein given its one-dimensional amino acid sequence. We use the HP model for protein folding proposed by Dill [7], which...
The Architecture of a Software Library for String Processing (1997)
Czumaj Ferragina, A. Czumaj, P. Ferragina, S. Muthukrishnan, J. L. Traff
We present our project to develop a software library of basic tools and data structures for string processing. Our goal is to provide an environment for testing new algorithms as well as for...
The Architecture of a Software Library for String Processing (1997)
A. Czumaj, P. Ferragina, L. Gasieniec, S. Muthukrishnan, J.L. Träff
We present our project to develop a software library of basic tools and data structures for string processing. Our goal is to provide an environment for testing new algorithms as well as for...
Engineering Diffusive Load Balancing Algorithms Using Experiments (1997)
Ralf Diekmann, S. Muthukrishnan, Madhu V. Nayakkankuppam
. We study a distributed load balancing problem on arbitrary graphs. First Order (FO) and Second Order (SO) schemes are popular local diffusive schedules for this problem. To use them, several...
Richa Agarwala, Serafim Batzoglou, Scott E. Decatur, Martin Farach, Sridhar Hannenhalli, S. Muthukrishnan
Richa Agarwala y Serafim Batzoglou z Vlado Danc'ik x Scott E. Decatur -- Martin Farach k Sridhar Hannenhalli S. Muthukrishnan yy Steven Skiena zz A long standing problem in molecular biology is...
Parallel scheduling problems in next generation wireless networks (1997)
L. Becchetti, S. Leonardi, A. Marchetti-spaccamela, A. Vitaletti, S. Diggavi, S. Muthukrishnan, ...
Next-generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users...
Optimal logarithmic time randomized suffix tree construction (1996)
Martin Farach, S. Muthukrishnan
The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential...
Perfect hashing for strings: Formalization and Algorithms (1996)
Martin Farach Muthukrishnan, Martin Farach, S. Muthukrishnan
Numbers and strings are two objects manipulated by most programs. Hashing has been well-studied for numbers and it has been effective in practice. In contrast, basic hashing issues for strings remain...
Perfect hashing for strings: Formalization and Algorithms (1996)
Martin Farach, S. Muthukrishnan
Numbers and strings are two objects manipulated by most programs. Hashing has been well-studied for numbers and it has been effective in practice. In contrast, basic hashing issues for strings remain...
Efficient dynamic method-lookup for object oriented languages (Extended Abstract) (1996)
Paolo Ferragina, S. Muthukrishnan
) Paolo Ferragina 1 and S. Muthukrishnan 2 1 Dipartimento di Informatica, Universit`a di Pisa, Italy. ferragin@di.unipi.it 2 Dept. of Computer Science, Univ. of Warwick, UK. muthu@dcs.warwick.ac.uk 1...
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...
Time and Space Efficient Method-Lookup for Object-Oriented Programs (Extended Abstract) (1996)
S. Muthukrishnan, Martin Müller
) S. Muthukrishnan Martin Muller y DIMACS & Univ. of Warwick University of New Mexico 1 Introduction Object-oriented languages (OOLs) are becoming increasingly popular in software development...
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...
Optimal Logarithmic Time Randomized Suffix Tree Construction (1996)
Martin Farach, S. Muthukrishnan
The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential...
Computing similarity between RNA strings (1996)
V. Bafna, S. Muthukrishnan, R. Ravi
Ribonucleic acid (RNA) strings are strings over the four-letter alphabet fA; C; G; Ug with a secondary structure of base-pairing between A0U and C 0G pairs in the string. Edges are drawn between two...
Group testing problems in experimental molecular biology (1995)
In group testing, the task is to determine the distinguished members of a set of objects L by asking subset queries of the form "does the set Q ` L contain a distinguished object?"...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh Leighton, Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Optimal Parallel Dictionary Matching and Compression (Extended Abstract) (1995)
Martin Farach, S. Muthukrishnan
) Martin Farach S. Muthukrishnan y Rutgers University DIMACS April 26, 1995 Abstract Emerging applications in multi-media and the Human Genome Project require storage and searching of large databases...
Faster Schedules for Diffusive Load Balancing via Over-Relaxation (1995)
Bhaskar Ghosh, S. Muthukrishnan, Martin H. Schultz
Consider the following load balancing problem. We are given a graph with arbitrary topology and an arbitrary load distribution on the nodes. In each time step, a node can send any amount of load to...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Group Testing Problems in Experimental Molecular Biology (1995)
Introduction In group testing, the task is to determine the distinguished members of a set of objects L by asking subset queries of the form "does the set Q ` L contain a distinguished...
Alphabet Dependence in Parameterized Matching (1994)
Amihood Amir Martin, Martin Farach, S. Muthukrishnan
The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set \Sigma. A recently introduced model is that of...
Alphabet Dependence in Parameterized Matching (1994)
Amihood Amir, Martin Farach, S. Muthukrishnan
The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set \Sigma. A recently introduced model is that of...
Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, ...
All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that...
Alphabet Dependence in Parameterized Matching (1993)
Amihood Amir, Martin Farach, S. Muthukrishnan
The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set #. A recently introduced model is that of...
Alphabet Dependence in Parameterized Matching (1993)
Amir, Amihood, Farach-Colton, Martin, Muthukrishnan, S.
The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set ∑. A recently introduced model is that of...
On Approximating Rectangle Tiling and Packing
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and...
On Approximating Rectangle Tiling and Packing
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and...
On Approximating Rectangle Tiling and Packing
Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
Our study of tiling and packing with rectangles in twodimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and...