LOTUS: locality optimizing triangle counting

Mohsen Koohi Esfahani, Peter Kilpatrick, Hans Vandierendonck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)
165 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.5X faster than previous works.

Original languageEnglish
Title of host publicationProceedings of the 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2022
PublisherAssociation for Computing Machinery
Pages219-233
Number of pages15
ISBN (Print)9781450392044
DOIs
Publication statusPublished - 06 Apr 2022

Keywords

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

Fingerprint

Dive into the research topics of 'LOTUS: locality optimizing triangle counting'. Together they form a unique fingerprint.

Cite this