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

Showing 2011 · cs.DSShow all

2 papers · 2 filters

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…