Computer Science – Data Structures and Algorithms
Scientific paper
2008-11-21
Computer Science
Data Structures and Algorithms
added content; modified L_0 algorithm -- ParityLogEstimator in version 1 contained an error, and the new algorithm uses slight
Scientific paper
The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows. There is a vector x which starts at 0, and many updates of the form x_i <-- x_i + v come sequentially in a stream. The algorithm also receives an error parameter 0 < eps < 1. The goal is then to output an approximation with relative error at most eps to F_p = ||x||_p^p. Previously, it was known that polylogarithmic space (in the vector length n) was achievable if and only if p <= 2. We make several new contributions in this regime, including: (*) An optimal space algorithm for 0 < p < 2, which, unlike previous algorithms which had optimal dependence on 1/eps but sub-optimal dependence on n, does not rely on a generic pseudorandom generator. (*) A near-optimal space algorithm for p = 0 with optimal update and query time. (*) A near-optimal space algorithm for the "distinct elements" problem (p = 0 and all updates have v = 1) with optimal update and query time. (*) Improved L_2 --> L_2 dimensionality reduction in a stream. (*) New 1-pass lower bounds to show optimality and near-optimality of our algorithms, as well as of some previous algorithms (the "AMS sketch" for p = 2, and the L_1-difference algorithm of Feigenbaum et al.). As corollaries of our work, we also obtain a few separations in the complexity of moment estimation problems: F_0 in 1 pass vs. 2 passes, p = 0 vs. p > 0, and F_0 with strictly positive updates vs. arbitrary updates.
Kane Daniel M.
Nelson Jelani
Woodruff David P.
No associations
LandOfFree
Revisiting Norm Estimation in Data Streams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Revisiting Norm Estimation in Data Streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Revisiting Norm Estimation in Data Streams will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-721341