2010/05/07 by Šumit Ganguly, Sumit Ganguly, Ganguly, Sumit
Computer Science · Decision Sciences · #Advanced Statistical Process Monitoring #Data Stream Mining Techniques #Distributed Sensor Networks and Detection Algorithms #cs.DS #cs.LG
paper · pdf · doi:10.48550/arxiv.1005.1120
Withdrawn due to error in analysis
arxiv created 2010/06/18 · arxiv updated 2010/06/21
For each p ∈ (0,2], we present a randomized algorithm that returns an ε-approximation of the pth frequency moment of a data stream Fp = ∑i = 1n \absfip. The algorithm requires space O(ε-2 log (mM)(log n)) and processes each stream update using time O((log n) (log ε-1)). It is nearly optimal in terms of space (lower bound O(ε-2 log (mM)) as well as time and is the first algorithm with these properties. The technique separates heavy hitters from the remaining items in the stream using an appropriate threshold and estimates the contribution of the heavy hitters and the light elements to Fp separately. A key component is the design of an unbiased estimator for \absfip whose data structure has low update time and low variance.