Publication: Multicore triangle computations without tuning
Issued Date
2015-01-01
Resource Type
ISSN
10844627
Other identifier(s)
2-s2.0-84940827497
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Proceedings - International Conference on Data Engineering. Vol.2015-May, (2015), 149-160
Suggested Citation
Julian Shun, Kanat Tangwongsan Multicore triangle computations without tuning. Proceedings - International Conference on Data Engineering. Vol.2015-May, (2015), 149-160. doi:10.1109/ICDE.2015.7113280 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/35832
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Multicore triangle computations without tuning
Author(s)
Other Contributor(s)
Abstract
© 2015 IEEE. Triangle counting and enumeration has emerged as a basic tool in large-scale network analysis, fueling the development of algorithms that scale to massive graphs. Most of the existing algorithms, however, are designed for the distributed-memory setting or the external-memory setting, and cannot take full advantage of a multicore machine, whose capacity has grown to accommodate even the largest of real-world graphs. This paper describes the design and implementation of simple and fast multicore parallel algorithms for exact, as well as approximate, triangle counting and other triangle computations that scale to billions of nodes and edges. Our algorithms are provably cache-friendly, easy to implement in a language that supports dynamic parallelism, such as Cilk Plus or OpenMP, and do not require parameter tuning. On a 40-core machine with two-way hyper-threading, our parallel exact global and local triangle counting algorithms obtain speedups of 17-50x on a set of real-world and synthetic graphs, and are faster than previous parallel exact triangle counting algorithms. We can compute the exact triangle count of the Yahoo Web graph (over 6 billion edges) in under 1.5 minutes. In addition, for approximate triangle counting, we are able to approximate the count for the Yahoo graph to within 99.6% accuracy in under 10 seconds, and for a given accuracy we are much faster than existing parallel approximate triangle counting implementations.