Improving I/O Complexity of Triangle Enumeration Conference Paper uri icon

abstract

  • 2017 IEEE. In the age of big data, many graph algorithms are now required to operate in external memory and deliver performance that does not significantly degrade with the scale of the problem. One particular area that frequently deals with graphs larger than RAM is triangle listing, where the algorithms must carefully piece together edges from multiple partitions to detect cycles. In recent literature, two competing proposals (i.e., Pagh and PCF) have emerged; however, neither one is universally better than the other. Since little is known about the I/O cost of PCF or how these methods compare to each other, we undertake an investigation into the properties of these algorithms, model their I/O cost, understand their shortcomings, and shed light on the conditions under which each method defeats the other. This insight leads us to develop a novel framework we call Trigon that surpasses the I/O performance of both previous techniques in all graphs and under all RAM conditions.

name of conference

  • 2017 IEEE International Conference on Data Mining (ICDM)

published proceedings

  • 2017 17TH IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM)

author list (cited authors)

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

citation count

  • 5

complete list of authors

  • Cui, Yi||Xiao, Di||Cline, Daren BH||Loguinov, Dmitri

editor list (cited editors)

  • Raghavan, V., Aluru, S., Karypis, G., Miele, L., & Wu, X.

publication date

  • November 2017