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.

Deterministic, Fast and Accurate Solution of the Heavy Hitters q-Tail Latencies Problem

Fornaio A.
Software
;
Epicoco I.
Conceptualization
;
Pulimeno M.
Conceptualization
;
Cafaro M.
Conceptualization
2022-01-01

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/476084
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact