On Efficient External-Memory Triangle Listing Conference Paper uri icon

abstract

  • 2016 IEEE. Discovering triangles in large graphs is a well-studied area, however, both external-memory performance of existing methods and our understanding of the complexity involved leave much room for improvement. To shed light on this problem, we first generalize the existing in-memory algorithms into a single framework of 18 triangle-search techniques. We then develop a novel external-memory approach, which we call Pruned Companion Files (PCF), that supports operation of all 18 algorithms, while significantly reducing I/O compared to the common methods in this area. After finding the best node-Traversal order, we build an implementation around it using SIMD instructions for list intersection and PCF for I/O. This method runs 5-10 times faster than the best available implementation and exhibits orders of magnitude less I/O. In one of our graphs, the program finds 1 trillion triangles in 237 seconds using a desktop CPU.

name of conference

  • 2016 IEEE 16th International Conference on Data Mining (ICDM)

published proceedings

  • 2016 IEEE 16TH INTERNATIONAL CONFERENCE ON DATA MINING (ICDM)

author list (cited authors)

  • Cui, Y. i., Xiao, D. i., & Loguinov, D.

citation count

  • 10

complete list of authors

  • Cui, Yi||Xiao, Di||Loguinov, Dmitri

editor list (cited editors)

  • Bonchi, F., Domingo-Ferrer, J., Baeza-Yates, R. A., Zhou, Z., & Wu, X.

publication date

  • December 2016