SAPCo Sort: optimizing degree-ordering for power-law graphs

Mohsen Koohi Esfahani, Peter Kilpatrick, Hans Vandierendonck

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

2 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages3
ISBN (Electronic)9781665459549
ISBN (Print)9781665459556
DOIs
Publication statusPublished - 27 Jun 2022
EventIEEE International Symposium on Performance Analysis of Systems and Software - Singapore, hybrid, Singapore
Duration: 22 May 202224 May 2022
http://ispass.org

Publication series

NameIEEE International Symposium on Performance Analysis of Systems and Software: Proceedings

Conference

ConferenceIEEE International Symposium on Performance Analysis of Systems and Software
Abbreviated titleISPASS
Country/TerritorySingapore
Period22/05/202224/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.

Cite this