Sumit Ganguly

activity

20062018

most citedA Lower Bound for Estimating High Moments of a Data Stream

12 citations · 13 across the 7 of their papers we have counts for

collaborators

10 papers

cs.DS2018

High Probability Frequency Moment Sketches

Sumit Ganguly, David P. Woodruff

We consider the problem of sketching the $p$ -th frequency moment of a vector, $p > 2$ , with multiplicative error at most $1 \pm ε$ and \emph{with high confidence} $1 - δ$ . Despite the l…

cs.DS2015

Taylor Polynomial Estimator for Estimating Frequency Moments

Sumit Ganguly

We present a randomized algorithm for estimating the $p$ th moment $F_{p}$ of the frequency vector of a data stream in the general update (turnstile) model to within a multiplicative…

cs.DS2011★ 12 cited

A Lower Bound for Estimating High Moments of a Data Stream

Sumit Ganguly

We show an improved lower bound for the Fp estimation problem in a data stream setting for p>2. A data stream is a sequence of items from the domain [n] with possible repetitions.…

cs.DS2011

Polynomial Estimators for High Frequency Moments

Sumit Ganguly

We present an algorithm for computing $F_{p}$ , the $p$ th moment of an $n$ -dimensional frequency vector of a data stream, for $2 < p < lo g (n)$ , to within $1 \pm ε$ factors, $ε\in [n…

cs.DS2010

Estimating small moments of data stream in nearly optimal space-time

Sumit Ganguly

For each $p \in (0, 2]$ , we present a randomized algorithm that returns an $ε$ -approximation of the $p$ th frequency moment of a data stream $F_p = \sum_{i = 1}^n \abs{f_i}^p$. The a…

cs.DS2010

Estimating small frequency moments of data stream: a characteristic function approach

Sumit Ganguly, Purushottam Kar

A data stream is viewed as a sequence of $M$ updates of the form $(index, i, v)$ to an $n$ -dimensional integer frequency vector $f$ , where the update changes $f_{i}$ to $f_i + v…