Campus Units

Electrical and Computer Engineering

Document Type

Article

Publication Date

11-2015

Journal or Book Title

Fronties in ICT

Volume

2

First Page

Article 23

DOI

10.3389/fict.2015.00023

Abstract

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.

Comments

This is an article from Frontiers in ICT 2 (2015): Article 23, doi: 10.3389/fict.2015.00023. Posted with permission.

Rights

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Copyright Owner

Singh and Tirthapura

Language

en

File Format

application/pdf

Share

COinS