Paper Info
Title
Sliding Sketches: A Framework using Time Zones for Data Stream Processing in Sliding Windows
Abstract
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.
Year
DOI
Venue
2020
10.1145/3394486.3403144
KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining Virtual Event CA USA July, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-7998-4
2
PageRank 
References 
Authors
0.37
21
8
Name
Order
Citations
PageRank
Xiangyang Gou191.84
Long He24612.49
Yinda Zhang371.44
Ke Wang4182.72
Xilai Liu520.71
Tong Yang620837.35
Yi Wang73514.57
Bin Cui81843124.59