Publication: Parallel streaming frequency-based aggregates
1
Issued Date
2014-01-01
Resource Type
Other identifier(s)
2-s2.0-84904514402
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Annual ACM Symposium on Parallelism in Algorithms and Architectures. (2014), 236-245
Suggested Citation
Kanat Tangwongsan, Srikanta Tirthapura, Kun Lung Wu Parallel streaming frequency-based aggregates. Annual ACM Symposium on Parallelism in Algorithms and Architectures. (2014), 236-245. doi:10.1145/2612669.2612695 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/33760
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Parallel streaming frequency-based aggregates
Author(s)
Other Contributor(s)
Abstract
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.