Projects per year
Abstract
Triangle Counting (TC) is a basic graph mining problem with numerous applications. However, the large size of realworld 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 realworld graphs on TC and make novel observations on how memory locality is negatively affected. Based on this, we introduce the LOTUS algorithm as a structureaware TC that optimizes locality.
The evaluation on 14 realworld graphs with up to 162 billion edges and on 3 different processor architectures of up to 128 cores shows that Lotus is 2.25.5X faster than previous works.
This paper studies the TC algorithm from the perspective of memory utilization. We investigate the implications of the skewed degree distribution of realworld graphs on TC and make novel observations on how memory locality is negatively affected. Based on this, we introduce the LOTUS algorithm as a structureaware TC that optimizes locality.
The evaluation on 14 realworld graphs with up to 162 billion edges and on 3 different processor architectures of up to 128 cores shows that Lotus is 2.25.5X faster than previous works.
Original language  English 

Title of host publication  Proceedings of the 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2022 
Publisher  Association for Computing Machinery 
Pages  219233 
Number of pages  15 
ISBN (Print)  9781450392044 
DOIs  
Publication status  Published  06 Apr 2022 
Keywords
 High Performance Computing
 Locality Optimizing
 Locality
 Triangle Counting
 Graph Algoirthms
 Memory Utlization
 Graph Processing
 KClique Problem
Fingerprint
Dive into the research topics of 'LOTUS: locality optimizing triangle counting'. Together they form a unique fingerprint.Projects
 2 Active

R1155CSC: DiPET: Distributed Stream Processing on Fog and Edge Systems via Transprecise Computing
Vandierendonck, H. & Varghese, B.
07/04/2020 → …
Project: Research

R1129ECI: Kelvin2  The High Performance Computing Centre in Northern Ireland (HPCNI)
Woods, R., Chevallier, O., Gillan, C., Hu, P., Rafferty, K., SaltoTellez, M., Tikhonova, I. & Vandierendonck, H.
04/12/2019 → …
Project: Research
Student theses

On designing structureaware highperformance graph algorithms
Author: Koohi Esfahani, M., Jul 2023Supervisor: Vandierendonck, H. (Supervisor) & Kilpatrick, P. (Supervisor)
Student thesis: Doctoral Thesis › Doctor of Philosophy
File