Incremental Maintenance of Maximal Cliques in a Dynamic Graph

dc.contributor.author Singh, Sneha Aman
dc.contributor.author Tirthapura, Srikanta
dc.contributor.author Tirthapura, Srikanta
dc.contributor.department Computer Science
dc.contributor.department Electrical and Computer Engineering
dc.date 2018-04-28T10:48:19.000
dc.date.accessioned 2020-06-30T02:02:30Z
dc.date.available 2020-06-30T02:02:30Z
dc.date.copyright Wed Jan 01 00:00:00 UTC 2014
dc.date.issued 2014-11-01
dc.description.abstract <p>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.</p>
dc.description.comments <p>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: <a href="http://dx.doi.org/10.1016/j.jpdc.2014.07.008" target="_blank">10.1016/j.jpdc.2014.07.008</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/ece_pubs/169/
dc.identifier.articleid 1175
dc.identifier.contextkey 12001321
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_pubs/169
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/20993
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/ece_pubs/169/2014_Tirthapura_MonitoringPersistent.pdf|||Fri Jan 14 21:07:46 UTC 2022
dc.source.uri 10.1016/j.jpdc.2014.07.008
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Databases and Information Systems
dc.subject.disciplines Electrical and Computer Engineering
dc.subject.disciplines Systems and Communications
dc.subject.keywords Distributed streams
dc.subject.keywords Persistent items
dc.title Incremental Maintenance of Maximal Cliques in a Dynamic Graph
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication b0235db2-0a72-4dd1-8d5f-08e5e2e2bf7d
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff
File
Original bundle
Now showing 1 - 1 of 1
Name:
2014_Tirthapura_MonitoringPersistent.pdf
Size:
466.79 KB
Format:
Adobe Portable Document Format
Description:
Collections