Incremental Maintenance of Maximal Cliques in a Dynamic Graph

Date
2014-11-01
Authors
Singh, Sneha Aman
Tirthapura, Srikanta
Tirthapura, Srikanta
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Department
Computer ScienceElectrical and Computer Engineering
Abstract

A persistent item in a stream is one that occurs regularly in the stream without necessarily contributing significantly to the volume of the stream. Persistent items are often associated with anomalies in network streams, such as botnet traffic and click fraud. While it is important to track persistent items in an online manner, it is challenging to zero-in on such items in a massive distributed stream. We present the first communication-efficient distributed algorithms for tracking persistent items in a data stream whose elements are partitioned across many different sites. We consider both infinite window and sliding window settings, and present algorithms that can track persistent items approximately with a probabilistic guarantee on the approximation error. Our algorithms have a provably low communication cost, and a low rate of false positives and false negatives, with a high probability. We present detailed results from an experimental evaluation that show the communication cost is small, and that the false positive and false negative rates are typically much lower than theoretical guarantees.

Comments

This is a manuscript of an article published as Singh, Sneha Aman, and Srikanta Tirthapura. "Monitoring persistent items in the union of distributed streams." Journal of Parallel and Distributed Computing 74, no. 11 (2014): 3115-3127. DOI: 10.1016/j.jpdc.2014.07.008. Posted with permission.

Description
Keywords
Citation
DOI
Collections