Skip to main content

14 Result(s)

within English Remove this filter Computer Science Remove this filter Algorithm Analysis and Problem Complexity Remove this filter Numeric Computing Remove this filter S. Muthukrishnan Remove this filter Chapter Remove this filter

and

  1. No Access

    Chapter and Conference Paper

    Nearly Optimal Private Convolution

    We study algorithms for computing the convolution of a private input x with a public input h, while satisfying the guarantees of (ε, δ)-differential privacy. Convolution is a fundamental operation, intimately rel...

    Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov in Algorithms – ESA 2013 (2013)

  2. No Access

    Chapter and Conference Paper

    Forty Years of Text Indexing

    This paper reviews the first 40 years in the life of textual inverted indexes, their many incarnations, and their applications. The paper is non-technical and assumes some familiarity with the structures and c...

    Alberto Apostolico, Maxime Crochemore… in Combinatorial Pattern Matching (2013)

  3. No Access

    Chapter

    Frugal Streaming for Estimating Quantiles

    Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. In many such applications, in fact, one needs to compute such statist...

    Qiang Ma, S. Muthukrishnan, Mark Sandler in Space-Efficient Data Structures, Streams, … (2013)

  4. No Access

    Chapter and Conference Paper

    Range Medians

    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 determine the me...

    Sariel Har-Peled, S. Muthukrishnan in Algorithms - ESA 2008 (2008)

  5. No Access

    Chapter and Conference Paper

    Radix Sorting with No Extra Space

    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,

    Gianni Franceschini, S. Muthukrishnan, Mihai Pǎtraşcu in Algorithms – ESA 2007 (2007)

  6. No Access

    Chapter and Conference Paper

    Bidding to the Top: VCG and Equilibria of Position-Based Auctions

    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 as their bid in the...

    Gagan Aggarwal, Jon Feldman, S. Muthukrishnan in Approximation and Online Algorithms (2007)

  7. No Access

    Chapter and Conference Paper

    Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods

    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 as a product of three ma...

    Petros Drineas, Michael W. Mahoney, S. Muthukrishnan in Algorithms – ESA 2006 (2006)

  8. No Access

    Chapter and Conference Paper

    Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

    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 A k ...

    Petros Drineas, Michael W. Mahoney… in Approximation, Randomization, and Combinat… (2006)

  9. No Access

    Chapter and Conference Paper

    Workload-Optimal Histograms on Streams

    A histogram is a piecewise-constant approximation of an observed data distribution. A histogram is used as a small-space, approximate synopsis of the underlying data distribution, which is often too large to b...

    S. Muthukrishnan, M. Strauss, X. Zheng in Algorithms – ESA 2005 (2005)

  10. No Access

    Chapter and Conference Paper

    Sublinear Methods for Detecting Periodic Trends in Data Streams

    We present sublinear algorithms — algorithms that use significantly less resources than needed to store or process the entire input stream – for discovering representative trends in data streams in the form of...

    Funda Ergun, S. Muthukrishnan, S. Cenk Sahinalp in LATIN 2004: Theoretical Informatics (2004)

  11. No Access

    Chapter and Conference Paper

    An Improved Data Stream Summary: The Count-Min Sketch and Its Applications

    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, range, and inner product que...

    Graham Cormode, S. Muthukrishnan in LATIN 2004: Theoretical Informatics (2004)

  12. No Access

    Chapter and Conference Paper

    Estimating Rarity and Similarity over Data Stream Windows

    In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations a t-(N-1), a t-(N-2), . . ...

    Mayur Datar, S. Muthukrishnan in Algorithms — ESA 2002 (2002)

  13. No Access

    Chapter and Conference Paper

    Range Searching in Categorical Data: Colored Range Searching on Grid

    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 asks for ...

    Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan in Algorithms — ESA 2002 (2002)

  14. No Access

    Chapter and Conference Paper

    Engineering diffusive load balancing algorithms using experiments

    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 parameters have to be...

    Ralf Diekmann, S. Muthukrishnan… in Solving Irregularly Structured Problems in… (1997)