Space‐efficient tracking of persistent items in a massive data stream

Tirthapura, Srikanta
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue

Motivated by scenarios in network anomaly detection, we consider the problem of detecting persistent items in a data stream, which are items that occur ‘regularly’ in the stream. In contrast with heavy hitters, persistent items do not necessarily contribute significantly to the volume of a stream, and may escape detection by traditional volume‐based anomaly detectors.

We first show that any online algorithm that tracks persistent items exactly must necessarily use a large workspace, and is infeasible to run on a traffic monitoring node. In light of this lower bound, we introduce an approximate formulation of the problem and present a small‐space algorithm to approximately track persistent items over a large data stream. We experimented with three different datasets to see how the accuracy and memory footprint of the algorithm varies with the skewness of the dataset. Our algorithms performed best for the two datasets out of three which had highest skewness of persistence and lowest mean persistence. To our knowledge, this is the first systematic study of the problem of detecting persistent items in a data stream, and our work can help detect anomalies that are temporal, rather than volume‐based.


This is the peer-reviewed version of the following article: Lahiri, Bibudh, Srikanta Tirthapura, and Jaideep Chandrashekar. "Space‐efficient tracking of persistent items in a massive data stream." Statistical Analysis and Data Mining: The ASA Data Science Journal 7, no. 1 (2014): 70-92, which has been published in final form at DOI:10.1002/sam.11214. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.

Data streams, persistence, sketches, hash-based filters