On Efficient External-Memory Triangle Listing Academic Article

abstract

• 2018 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 available implementations 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.

authors

• Loguinov, Dmitri

published proceedings

• IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING

author list (cited authors)

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

citation count

• 5

complete list of authors

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

publication date

• August 2019

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE Transactions on Knowledge and Data Engineering  Journal

keywords

• External Memory
• Graph Algorithms
• Triangle Listing

Digital Object Identifier (DOI)

• 10.1109/TKDE.2018.2858820

start page

• 1555

end page

• 1568

volume

• 31

issue

• 8

URL

• http://dx.doi.org/10.1109/tkde.2018.2858820