64 Downloads (Pure)

Abstract

Triangle Counting (TC) is a basic graph mining problem with numerous applications. However, the large size of real-world graphs has a severe effect on TC performance.

This paper studies the TC algorithm from the perspective of memory utilization. We investigate the implications of the skewed degree distribution of real-world graphs on TC and make novel observations on how memory locality is negatively affected. Based on this, we introduce the LOTUS algorithm as a structure-aware TC that optimizes locality.

The evaluation on 14 real-world graphs with up to 162 billion edges and on 3 different processor architectures of up to 128 cores shows that Lotus is 2.2-5.5 times faster than the previous works.


Original languageEnglish
Title of host publication27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP 2022): Proceedings
PublisherAssociation for Computing Machinery (ACM)
Pages219-233
Number of pages15
ISBN (Print)978-1-4503-9204-4
DOIs
Publication statusPublished - 06 Apr 2022

Keywords

  • High Performance Computing
  • Locality Optimizing
  • Locality
  • Triangle Counting
  • Graph Algoirthms
  • Memory Utlization
  • Graph Processing
  • K-Clique Problem

Cite this