SAPCo Sort: optimizing Degree-Ordering for Power-Law Graphs
SAPCo Sort: optimizing Degree-Ordering for Power-Law Graphs
复制标题
DOI：
10.1109/ispass55109.2022.00015
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Mohsen Koohi Esfahani;Peter Kilpatrick;Hans Vandierendonck
中科院分区：
文献类型：
--
作者：
Mohsen Koohi Esfahani;Peter Kilpatrick;Hans Vandierendonck
我们引入结构感知Parattet计数（SAPCo）排序算法，优化度排序的性能，这是图分析中的一个关键操作。SAPCo利用倾斜度分布来加速排序。对多达36亿个顶点的图的评估表明，SAPCo排序平均比最先进的排序算法（如计数排序，基数排序和样本排序）快1.7-33.5倍。
We introduce the Structure-Aware Parattet 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.