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.

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.

Copyright Owner

Wiley Periodicals, Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS