LOTUS: locality optimizing triangle counting

Mohsen Koohi Esfahani; Peter Kilpatrick; Hans Vandierendonck

doi:10.1145/3503221.3508402

LOTUS: locality optimizing triangle counting

Mohsen Koohi Esfahani, Peter Kilpatrick, Hans Vandierendonck

School of Electronics, Electrical Engineering and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 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 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	219-233
Number of pages	15
ISBN (Print)	9781450392044
DOIs	https://doi.org/10.1145/3503221.3508402
Publication status	Published - 06 Apr 2022

Keywords

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

Access to Document

10.1145/3503221.3508402Licence: Unspecified

R1155CSC: DiPET: Distributed Stream Processing on Fog and Edge Systems via Transprecise Computing
Vandierendonck, H. (PI) & Varghese, B. (CoI)
07/04/2020 → …
Project: Research
R1129ECI: Kelvin-2 - The High Performance Computing Centre in Northern Ireland (HPC-NI)
Woods, R. (PI), Chevallier, O. (CoI), Gillan, C. (CoI), Hu, P. (CoI), Rafferty, K. (CoI), Salto-Tellez, M. (CoI), Tikhonova, I. (CoI) & Vandierendonck, H. (CoI)
04/12/2019 → …
Project: Research

On designing structure-aware high-performance graph algorithms
Koohi Esfahani, M. (Author), Vandierendonck, H. (Supervisor) & Kilpatrick, P. (Supervisor), Jul 2023
Student thesis: Doctoral Thesis › Doctor of Philosophy

File

Cite this

@inproceedings{1e0faf30d3e44858bcc2fc866eec7d0a,

title = "LOTUS: locality optimizing triangle counting",

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.",

keywords = "High Performance Computing, Locality Optimizing, Locality, Triangle Counting, Graph Algoirthms, Memory Utlization, Graph Processing, K-Clique Problem",

author = "{Koohi Esfahani}, Mohsen and Peter Kilpatrick and Hans Vandierendonck",

year = "2022",

month = apr,

day = "6",

doi = "10.1145/3503221.3508402",

language = "English",

isbn = "9781450392044",

pages = "219--233",

booktitle = "Proceedings of the 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2022",

publisher = "Association for Computing Machinery",

address = "United States",

}

LOTUS: locality optimizing triangle counting. / Koohi Esfahani, Mohsen; Kilpatrick, Peter ; Vandierendonck, Hans.
Proceedings of the 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2022. Association for Computing Machinery, 2022. p. 219-233.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - LOTUS: locality optimizing triangle counting

AU - Koohi Esfahani, Mohsen

AU - Kilpatrick, Peter

AU - Vandierendonck, Hans

PY - 2022/4/6

Y1 - 2022/4/6

N2 - 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.

AB - 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.

KW - High Performance Computing

KW - Locality Optimizing

KW - Locality

KW - Triangle Counting

KW - Graph Algoirthms

KW - Memory Utlization

KW - Graph Processing

KW - K-Clique Problem

U2 - 10.1145/3503221.3508402

DO - 10.1145/3503221.3508402

M3 - Conference contribution

SN - 9781450392044

SP - 219

EP - 233

BT - Proceedings of the 27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2022

PB - Association for Computing Machinery

ER -

LOTUS: locality optimizing triangle counting

Abstract

Keywords

Access to Document

Fingerprint

Projects

R1155CSC: DiPET: Distributed Stream Processing on Fog and Edge Systems via Transprecise Computing

R1129ECI: Kelvin-2 - The High Performance Computing Centre in Northern Ireland (HPC-NI)

Student theses

On designing structure-aware high-performance graph algorithms

Cite this