ppSCAN: Parallelizing Pruning-based Graph Structural Clustering (ICPP'18) - by Yulin Che, Shixuan Sun and Prof. Qiong Luo
Parallel pSCAN algorithm with vectorized set intersection, compared with SCAN, pSCAN, SCAN++, anySCAN, SCAN-XP (an order of magnitude faster than the-state-of-the-arts), 250x faster than pSCAN on KNL (1.8 billion-undirected-edge-graph friendster).
See our slides for the general idea. Please check out our ICPP'18 paper Parallelizing Pruning-based Graph Structural Clustering for further details.
by Authors:
Yulin Che, Shixuan Sun and Prof. Luo.
ppSCAN is tested on both Multi-core Intel Xeon CPU and Intel Xeon Phi Processor Knights Landing.
content | directory |
---|---|
c++ parallel codes (Release) | see ppSCAN-release, removing experimental codes, tested on KNL (support dst_edge (neighbors) array allocated on MCDRAM, using memkind) |
c++ parallel codes | see ppSCAN |
vectorization codes (AVX2 / AVX512) | see Graph.cpp |
experimental scripts and case studies | see python_experiments |
python scripts for generating figures in paper | see python paper-figures |
SCAN variants codes | see SCANVariants: SCAN, pSCAN, SCAN++, anySCAN, SCAN-XP |
python scripts during study | see python_playground: union-find, galloping-search, pSCAN |
If you use our codes in your research, please kindly cite our paper. The BibTeX is as follows.
@inproceedings{DBLP:conf/icpp/CheSL18,
author = {Yulin Che and
Shixuan Sun and
Qiong Luo},
title = {Parallelizing Pruning-based Graph Structural Clustering},
booktitle = {Proceedings of the 47th International Conference on Parallel Processing,
{ICPP} 2018, Eugene, OR, USA, August 13-16, 2018},
pages = {77:1--77:10},
year = {2018},
crossref = {DBLP:conf/icpp/2018},
url = {http://doi.acm.org/10.1145/3225058.3225063},
doi = {10.1145/3225058.3225063},
timestamp = {Thu, 09 Aug 2018 08:53:38 +0200},
biburl = {https://dblp.org/rec/bib/conf/icpp/CheSL18},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
SCAN Preliminaries, our ppSCAN overview including design and optimizations.
Xu X, Yuruk N, Feng Z, et al. Scan: a structural clustering algorithm for networks[C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2007: 824-833.
Shiokawa H, Fujiwara Y, Onizuka M. SCAN++: efficient algorithm for finding clusters, hubs and outliers on large-scale graphs[J]. Proceedings of the VLDB Endowment, 2015, 8(11): 1178-1189.
Chang L, Li W, Qin L, et al. $\mathsf {pSCAN} $: Fast and Exact Structural Graph Clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(2): 387-401.
Mai S T, Dieu M S, Assent I, et al. Scalable and Interactive Graph Clustering Algorithm on Multicore CPUs[C]//Data Engineering (ICDE), 2017 IEEE 33rd International Conference on. IEEE, 2017: 349-360.
Takahashi T, Shiokawa H, Kitagawa H. SCAN-XP: Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Coprocessors[C]//Proceedings of the 2nd International Workshop on Network Data Analytics. ACM, 2017: 6.
Stovall T R, Kockara S, Avci R. GPUSCAN: GPU-Based Parallel Structural Clustering Algorithm for Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(12): 3381-3393.