We introduce FDCMSS, a novel sketch-based algorithm for frequent items working in the time fading model. The algorithm cleverly combines key ideas borrowed from forward decay, the Count-Min and the Space Saving algorithms.

We formally prove the correctness of our algorithm.

We experimentally validate the algorithm on synthetic data distributed using a Zipf distribution, and also on real datasets.

We compare the performances and the error committed by our algorithm against λ-HCount, an algorithm recently proposed by Chen and Mei. Extensive experimental results show that FDCMSS outperforms λ-HCount with regard to speed, space used, precision attained and error committed on both synthetic and real datasets.