Deterministic, Fast and Accurate Solution of the Heavy Hitters <italic>q</italic>-Tail Latencies Problem

Abstract

The heavy hitters $q$ -tail latencies problem has been introduced recently. This problem, framed in the context of data stream monitoring, requires approximating the quantiles of the heavy hitters items of an input stream whose elements are pairs (item, latency). The underlying rationale is that heavy hitters are obviously among the most important items to be monitored, and their associated latency quantiles are of extreme interest in several network monitoring applications. Currently, two randomized (SQUARE and SQUAD) and one deterministic (QUASI) algorithms are available to solve the problem. In this paper, we present a novel deterministic algorithm and empirically show that it outperforms QUASI, the current state of the art deterministic algorithm for the problem, with regard to accuracy and speed.

Keywords

• Data stream mining
• heavy hitters
• quantiles
• sketches