Projects per year
Abstract
We introduce the Structure-Aware Parallel Counting (SAPCo) Sort algorithm that optimizes performance of degree-ordering, a key operation in graph analytics. SAPCo leverages the skewed degree distribution to accelerate sorting. The evaluation for graphs of up to 3.6 billion vertices shows that SAPCo sort is, on average, 1.7-33.5 times faster than state-of-the-art sorting algorithms such as counting sort, radix sort, and sample sort.
Original language | English |
---|---|
Title of host publication | Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2022 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Number of pages | 3 |
ISBN (Electronic) | 9781665459549 |
ISBN (Print) | 9781665459556 |
DOIs | |
Publication status | Published - 27 Jun 2022 |
Event | IEEE International Symposium on Performance Analysis of Systems and Software - Singapore, hybrid, Singapore Duration: 22 May 2022 → 24 May 2022 http://ispass.org |
Publication series
Name | IEEE International Symposium on Performance Analysis of Systems and Software: Proceedings |
---|
Conference
Conference | IEEE International Symposium on Performance Analysis of Systems and Software |
---|---|
Abbreviated title | ISPASS |
Country/Territory | Singapore |
Period | 22/05/2022 → 24/05/2022 |
Internet address |
Keywords
- High Performance Computing
- Graph Algorithms
- Degree-Ordering
- Sorting Algorithms
- Real-World Graphs
- Structure-Aware Algorithms
Fingerprint
Dive into the research topics of 'SAPCo Sort: optimizing degree-ordering for power-law graphs'. Together they form a unique fingerprint.Projects
- 2 Active
-
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
Student theses
-
On designing structure-aware high-performance graph algorithms
Koohi Esfahani, M. (Author), Vandierendonck, H. (Supervisor) & Kilpatrick, P. (Supervisor), Jul 2023Student thesis: Doctoral Thesis › Doctor of Philosophy
File