Name
Abstract | ||
|---|---|---|
We present a randomized algorithm for estimating the pth moment F-p of the frequency vector of a data stream in the general update (turnstile) model to within a multiplicative factor of 1 + epsilon, for p > 2, with high constant confidence. For 0 < epsilon <= 1, the algorithm uses space O(n(1-2/p) epsilon(-2) + n(1-2/p) epsilon(-4)/(p) log(n)) words. This improves over the current bound of O(n(1-2/p) epsilon (-2-4/p) log(n)) words by Andoni et al. in [2]. Our space upper bound matches the lower bound of Li and Woodruff [17] for epsilon = (log(n))(-Omega(1)) and the lower bound of Andoni et al. [3] for epsilon = Omega(1). |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-47672-7_44 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Discrete mathematics,Randomized algorithm,Frequency moments,Combinatorics,Multiplicative function,Turnstile,Upper and lower bounds,Omega,Mathematics,Taylor series,Estimator | Journal | 9134 |
ISSN | Citations | PageRank |
0302-9743 | 6 | 0.41 |
References | Authors | |
9 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sumit Ganguly | 1 | 813 | 236.01 |