An Evaluation of Streaming Algorithms for Distinct Counting Over a Sliding Window

Frontiers in ICT

Singh, Sneha Aman¹  Tirthapura, Srikanta¹ 

[1] Department of Electrical and Computer Engineering, Iowa State University, USA

关键词: distinct counting;    data stream algorithms;    sliding window;    real-time analytics;    experimental evaluation;   

DOI  :  10.3389/fict.2015.00023

学科分类：计算机网络和通讯

来源: Frontiers

【 摘 要 】

Counting the number of distinct elements in a data stream (``distinct counting'') is a fundamental aggregation task in database query processing, query optimization and network monitoring. On a stream of elements, it is commonly needed to compute an aggregate over only the most recent elements, leading to the problem of distinct counting over a ``sliding window'' of the stream. We present a detailed experimental study of the performance of different algorithms for distinct counting over a sliding window. We observe that the performance of an algorithm depends on the basic method used, as well as aspects such as the hash function, the mix of query and updates, and the method used to boost accuracy. We compare the performance of prominent algorithms, and evaluate the influence of these factors, leading to practical recommendations for implementation. To the best of our knowledge, this is the first detailed experimental study of distinct counting over a sliding window.

【 授权许可】

CC BY