Differentiating set intersections in maximal clique enumeration by function and subproblem size

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

Abstract

Clique finding problems such as maximal clique enumeration are computationally challenging due to the combinatorial number of vertex sets that need to be evaluated. Despite prior advances, the majority of execution time is still spent in set intersections, which limits the speed of the algorithms and their application to increasingly larger graphs. To address this issue, we propose to differentiate the set intersection algorithm to its function and the problem size, leading to several innovations: (i) a new primitive “intersect-size-exceeds” which short-cuts the calculation of the size of an intersection if it does not exceed a pre-determined threshold; (ii) a new data structure that supports efficient hash-based intersec- tion on constantly evolving sets; and (iii) efficient specialized variants of clique search and intersection for “small” and “tiny” subproblems. Compared to the state-of-the-art maximal clique search algorithms by Blanusa et al (VLDB 2020) and Besta et al (MICRO 2021), a median speedup is observed of 4.14× and 10.91× on AMD Zen Version 2, and a median speedup of 3.44× and 8.26× on Intel Sapphire Rapids over 14 challenging graph datasets.
Original languageEnglish
Title of host publicationProceedings of the 38th ACM International Conference on Supercomputing: ICS 2024
Number of pages14
DOIs
Publication statusAccepted - 03 Apr 2024
EventACM International Conference on Supercomputing 2024 - Kyoto, Japan
Duration: 04 Jun 202407 Jun 2024
Conference number: 38
https://ics2024.github.io

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

ConferenceACM International Conference on Supercomputing 2024
Abbreviated titleICS
Country/TerritoryJapan
CityKyoto
Period04/06/202407/06/2024
Internet address

Fingerprint

Dive into the research topics of 'Differentiating set intersections in maximal clique enumeration by function and subproblem size'. Together they form a unique fingerprint.

Cite this