Computer Science, Electrical and Computer Engineering
26th ACM Symposium on Parallelism in Algorithms and Architectures
Link to Published Version
Journal or Book Title
Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures
June 23-25, 2014
Prague, Czech Republic
We present efficient parallel streaming algorithms for fundamental frequency-based aggregates in both the sliding window and the infinite window settings. In the sliding window setting, we give a parallel algorithm for maintaining a space-bounded block counter (SBBC). Using SBBC, we derive algorithms for basic counting, frequency estimation, and heavy hitters that perform no more work than their best sequential counterparts. In the infinite window setting, we present algorithms for frequency estimation, heavy hitters, and count-min sketch. For both the infinite window and sliding window settings, our parallel algorithms process a "minibatch" of items using linear work and polylog parallel depth. We also prove a lower bound showing that the work of the parallel algorithm is optimal in the case of heavy hitters and frequency estimation. To our knowledge, these are the first parallel algorithms for these problems that are provably work efficient and have low depth.
Tangwongsan, Kanat; Tirthapura, Srikanta; and IBM T. J. Watson Research Center, "Parallel Streaming Frequency-Based Aggregates" (2014). Electrical and Computer Engineering Conference Papers, Posters and Presentations. 59.