Parallel Triangle Counting in Massive Streaming Graphs

dc.contributor.author Pavan, A.
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-29T20:14:46.000
dc.date.accessioned 2020-06-30T02:01:41Z
dc.date.available 2020-06-30T02:01:41Z
dc.date.copyright Tue Jan 01 00:00:00 UTC 2013
dc.date.embargo 2018-04-24
dc.date.issued 2013-01-01
dc.description.abstract <p>The number of triangles in a graph is a fundamental metric widely used in social network analysis, link classification and recommendation, and more. In these applications, modern graphs of interest tend to both large and dynamic. This paper presents the design and implementation of a fast parallel algorithm for estimating the number of triangles in a massive undirected graph whose edges arrive as a stream. Our algorithm is designed for shared-memory multicore machines and can make efficient use of parallelism and the memory hierarchy. We provide theoretical guarantees on performance and accuracy, and our experiments on real-world datasets show accurate results and substantial speedups compared to an optimized sequential implementation.</p>
dc.description.comments <p>This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Tangwongsan, Kanat, Aduri Pavan, and Srikanta Tirthapura. "Parallel triangle counting in massive streaming graphs." In <em>Proceedings of the 22nd ACM International Conference on Information & Knowledge Management</em>, (2013): 781-786. DOI:<a href="http://dx.doi.org/10.1145/2505515.2505741" target="_blank">10.1145/2505515.2505741</a>. </p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/ece_conf/57/
dc.identifier.articleid 1056
dc.identifier.contextkey 12012992
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_conf/57
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/20880
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/ece_conf/57/2013_Tirthapura_ParallelTriangle.pdf|||Sat Jan 15 00:59:08 UTC 2022
dc.source.uri 10.1145/2505515.2505741
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.title Parallel Triangle Counting in Massive Streaming Graphs
dc.type article
dc.type.genre conference
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:
2013_Tirthapura_ParallelTriangle.pdf
Size:
318.52 KB
Format:
Adobe Portable Document Format
Description: