A Sketch Framework for Approximate Data Stream Processing in Sliding Windows

Gou，Xiangyang1; Zhang，Yinda2; Hu，Zhoujing3; He，Long3; Wang，Ke3; Liu，Xilai3; Yang，Tong4; Wang，Yi5; Cui，Bin6

2022

10.1109/TKDE.2022.3151140

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING   影响因子和分区

1041-4347

1558-2191

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 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 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 Approximation algorithms Art Big Data Computer science Data models data stream Hash functions Probabilistic logic sketch sliding window

EI ; SCI

英语

其他

20220811686543

Approximation algorithms ; Big data ; Communication channels (information theory) ; Data handling ; Decoding ; Probabilistic logics ; Query processing ; Trellis codes

Information Theory and Signal Processing:716.1 ; Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Data Processing and Image Processing:723.2 ; Mathematics:921

ENGINEERING

2-s2.0-85124827375

Scopus

1.WICT, Peking University, 12465 Beijing, Beijing, China,
2.Engineering and Computer Sciences, Peking University, 12465 Beijing, Beijing, China,
3.Computer Science Department, Peking University, 12465 Beijing, Hebei, China,
4.Computer Science Department, Peking University, 12465 Beijing, Hebei, China, 100871
5.CS Dept, Southern University of Science and Technology, 255310 Shenzhen, Guangdong, China,
6.Computer Science and Technology, Peking University, 12465 Beijing, Beijing, China,

Gou，Xiangyang,Zhang，Yinda,Hu，Zhoujing,et al. A Sketch Framework for Approximate Data Stream Processing in Sliding Windows[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2022,PP(99):1-1.

Gou，Xiangyang.,Zhang，Yinda.,Hu，Zhoujing.,He，Long.,Wang，Ke.,...&Cui，Bin.(2022).A Sketch Framework for Approximate Data Stream Processing in Sliding Windows.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,PP(99),1-1.

Gou，Xiangyang,et al."A Sketch Framework for Approximate Data Stream Processing in Sliding Windows".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING PP.99(2022):1-1.