Scalable and Interactive Graph Clustering Algorithm on Multicore CPUs

Thai Son Mai, Martin Storgaard Dieu, Ira Assent, Jon Jacobsen, Jesper Kristensen, Mathias Birk

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

15 Citations (Scopus)

Abstract

The structural graph clustering algorithm SCAN is a fundamental technique for managing and analyzing graph data. However, its high runtime remains a computational bottleneck, which limits its applicability. In this paper, we propose a novel interactive approach for tackling this problem on multicore CPUs. Our algorithm, called anySCAN, iteratively processes vertices in blocks. The acquired results are merged into an underlying cluster structures consisting of the so-called supernodes for building clusters. During its runtime, anySCAN can be
suppressed for examining intermediate results and resumed for finding better result at arbitrary time points, making it an anytime algorithm which is capable to deal with very large graphs in an interactive way and under arbitrary time constraints. Moreover, its block processing scheme allows the design of a scalable parallel algorithm on shared memory architectures such as multicore
CPUs for further speeding up the algorithm at each iteration. Consequently, anySCAN uniquely is an interactive and parallel algorithm at the same time. Experiments are conducted on very large real graph datasets for demonstrating the performance of anySCAN. It acquires very good approximate results early,
leading to orders of magnitude speedup factor compared to SCAN and its variants. Using 16 threads, the acquired speed up factors are up to ≈ 13.5 times over its sequential version.
Original languageEnglish
Title of host publicationIEEE International Conference on Data Engineering (ICDE)
Pages349-360
Number of pages12
DOIs
Publication statusPublished - 2017
Externally publishedYes

Keywords

  • Structural graph clustering
  • SCAN
  • anytime clustering
  • parallel algorithm
  • multicore CPUs

Fingerprint Dive into the research topics of 'Scalable and Interactive Graph Clustering Algorithm on Multicore CPUs'. Together they form a unique fingerprint.

  • Cite this

    Mai, T. S., Storgaard Dieu, M., Assent, I., Jacobsen, J., Kristensen, J., & Birk, M. (2017). Scalable and Interactive Graph Clustering Algorithm on Multicore CPUs. In IEEE International Conference on Data Engineering (ICDE) (pp. 349-360) https://doi.org/10.1109/ICDE.2017.94