A Sketch Framework for Approximate Data Stream Processing in Sliding Windows

摘要

Data stream processing has become a hot issue in recent years. There are three fundamental stream processing tasks: membership query, frequency query, and Top-K 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 the Sliding sketch, 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 the accuracy of existing sketches that do not support sliding windows becomes much higher than the corresponding prior art after using our framework. We released all the source code at Github.