The problem of mining Correlated Heavy Hitters (CHH) from a two- dimensional data stream has been introduced recently, and a deterministic algo- rithm based on the use of the Misra–Gries algorithm has been proposed by Lahiri et al. to solve it. In this paper we present a new counter-based algorithm for tracking CHHs, formally prove its error bounds and correctness and show, through exten- sive experimental results, that our algorithm outperforms the Misra–Gries based algorithm with regard to accuracy and speed whilst requiring asymptotically much less space.
Titolo: | Fast and Accurate Mining of Correlated Heavy Hitters |
Autori: | PULIMENO, MARCO [Methodology] |
Data di pubblicazione: | 2018 |
Rivista: | |
Abstract: | The problem of mining Correlated Heavy Hitters (CHH) from a two- dimensional data stream has been introduced recently, and a deterministic algo- rithm based on the use of the Misra–Gries algorithm has been proposed by Lahiri et al. to solve it. In this paper we present a new counter-based algorithm for tracking CHHs, formally prove its error bounds and correctness and show, through exten- sive experimental results, that our algorithm outperforms the Misra–Gries based algorithm with regard to accuracy and speed whilst requiring asymptotically much less space. |
Handle: | http://hdl.handle.net/11587/413212 |
Appare nelle tipologie: | Articolo pubblicato su Rivista |
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.