Fast and Accurate Mining of Correlated Heavy Hitters

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.