Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Conference Proceeding

Conference

22nd ACM International Conference on Information & Knowledge Management (CIKM '13)

Publication Version

Accepted Manuscript

Link to Published Version

https://doi.org/10.1145/2505515.2505741

Publication Date

2013

Journal or Book Title

Proceedings of the 22nd ACM International Conference on Information & Knowledge Management (CIKM '13)

First Page

781

Last Page

786

DOI

10.1145/2505515.2505741

Conference Date

October 27-November 1, 2013

City

San Francisco, CA

Abstract

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.

Comments

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 Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, (2013): 781-786. DOI:10.1145/2505515.2505741.

Copyright Owner

ACM

Language

en

File Format

application/pdf

Published Version

Share

Article Location

 
COinS