2010/05/05 by Šumit Ganguly, Sumit Ganguly, Purushottam Kar +2
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1005.0809
12 pages
arxiv created 2010/05/05 · openalex publication_date 2010/05/05 · arxiv updated 2015/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Estimating the first moment of a data stream defined as F1 = ∑_i ∈ \1, 2, …, n\ \absfi to within 1 ± ε-relative error with high probability is a basic and influential problem in data stream processing. A tight space bound of O(ε-2 log (mM)) is known from the work of [Kane-Nelson-Woodruff-SODA10]. However, all known algorithms for this problem require per-update stream processing time of Ω(ε-2), with the only exception being the algorithm of [Ganguly-Cormode-RANDOM07] that requires per-update processing time of O(log2(mM)(log n)) albeit with sub-optimal space O(ε-3log2(mM)). In this paper, we present an algorithm for estimating F1 that achieves near-optimality in both space and update processing time. The space requirement is O(ε-2(log n + (log ε-1)log(mM))) and the per-update processing time is O( (log n)log (ε-1)).