Campus Units
Electrical and Computer Engineering, Computer Science
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
2014
Journal or Book Title
Statistical Analysis and Data Mining: The ASA Data Science Journal
Volume
7
Issue
1
First Page
70
Last Page
92
DOI
10.1002/sam.11214
Abstract
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.
Copyright Owner
Wiley Periodicals, Inc.
Copyright Date
2013
Language
en
File Format
application/pdf
Recommended Citation
Impetus Technologies; Tirthapura, Srikanta; and Technicolor Labs, "Space‐efficient tracking of persistent items in a massive data stream" (2014). Electrical and Computer Engineering Publications. 177.
https://lib.dr.iastate.edu/ece_pubs/177
Comments
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.