Sliding Sketches: A Framework using Time Zones for Data Stream Processing in Sliding Windows

Gou，Xiangyang1; He，Long1; Zhang，Yinda1; Wang，Ke1; Liu，Xilai1; Yang，Tong1; Wang，Yi2; Cui，Bin1

10.1145/3394486.3403144

2020-08-23

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

1015-1025

Data stream processing has become a hot issue in recent years due to the arrival of big data era. There are three fundamental stream processing tasks: membership query, frequency query and heavy hitter query. While most existing solutions address these queries in fixed windows, this paper focuses on a more challenging task: answering these queries in sliding windows. While most existing solutions address different kinds of queries by using different algorithms, this paper focuses on a generic framework. In this paper, we propose a generic framework, namely Sliding sketches, which can be applied to many existing solutions for the above three queries, and enable them to support queries in sliding windows. We apply our framework to five state-of-the-art sketches for the above three kinds of queries. Theoretical analysis and extensive experimental results show that after using our framework, the accuracy of existing sketches that do not support sliding windows becomes much higher than the corresponding best prior art. We released all the source code at Github.

approximate query data stream sketch sliding window

其他

英语

EI

20203709168405

Data streams

Data Processing and Image Processing:723.2

2-s2.0-85090408988

Scopus

1.Peking University,Beijing,China
2.Southern University of Science and Technology,Shenzhen,China

Gou，Xiangyang,He，Long,Zhang，Yinda,et al. Sliding Sketches: A Framework using Time Zones for Data Stream Processing in Sliding Windows[C],2020:1015-1025.