12 citations · 13 across the 7 of their papers we have counts for
Showing 2010Show all
3 papers · 1 filter
cs.DS2010
Estimating small moments of data stream in nearly optimal space-time
Sumit Ganguly
For each , we present a randomized algorithm that returns an -approximation of the 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 updates of the form to an -dimensional integer frequency vector , where the update changes to $f_i + v…
cs.DS2010
On Estimating the First Frequency Moment of Data Streams
Sumit Ganguly, Purushottam Kar
Estimating the first moment of a data stream defined as $F_1 = \sum_{i \in \{1, 2, \ldots, n\}} \abs{f_i}$ to within -relative error with high probability is a basic and i…