Sliding Window Top-K Monitoring over Distributed Data Streams

Data Science and Engineering

Zhijin Lv¹  Ben Chen¹  Yang Liu¹  Xiaohui Yu² 

[1] School of Computer Science and Technology, Shandong University;School of Information Technology, York University;

关键词: Top-K;    Distributed monitoring;    Data stream;    Stream processing;   

DOI  :  10.1007/s41019-017-0053-1

来源: DOAJ

【 摘 要 】

Abstract Most of the traditional top-k algorithms are based on a single-server setting. They may be highly inefficient and/or cause huge communication overhead when applied to a distributed system environment. Therefore, the problem of top-k monitoring in distributed environments has been intensively investigated recently. This paper studies how to monitor the top-k data objects with the largest aggregate numeric values from distributed data streams within a fixed-size monitoring window W, while minimizing communication cost across the network. We propose a novel algorithm, which adaptively reallocates numeric values of data objects among distributed nodes by assigning revision factors when local constraints are violated and keeps the local top-k result at distributed nodes in line with the global top-k result. We also develop a framework that combines a distributed data stream monitoring architecture with a sliding window model. Based on this framework, extensive experiments are conducted on top of Apache Storm to verify the efficiency and scalability of the proposed algorithm.

【 授权许可】

Unknown