2024/06/17 by Wang, Yichuan · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2406.12149
We study the streaming complexity of k-counter approximate counting. In the k-counter approximate counting problem, we are given an input string in [k]n, and we are required to approximate the number of each j's (j∈[k]) in the string. Typically we require an additive error ≤(n)/(3(k-1)) for each j∈[k] respectively, and we are mostly interested in the regime n≫ k. We prove a lower bound result that the deterministic and worst-case k-counter approximate counting problem requires Ω(klog(n/k)) bits of space in the streaming model, while no non-trivial lower bounds were known before. In contrast, trivially counting the number of each j∈[k] uses O(klog n) bits of space. Our main proof technique is analyzing a novel potential function. Our lower bound for k-counter approximate counting also implies the optimality of some other streaming algorithms. For example, we show that the celebrated Misra-Gries algorithm for heavy hitters [MG82] has achieved optimal space usage.