HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs
Proceedings of the ACM on Management of Data · 12.03.2024 · 2 (1) · 1-25
DOI: 10.1145/3639284 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 26.03.2024. Verfasst von Boyu Yang und 4 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: Natural Science Foundation, National Natural Science Foundation of China, Shanghai Science and Technology Innovation Action Plan.
Abstract (Originalsprache)
As one of the most primitive operators in graph algorithms, such as the triangle counting, maximal clique enumeration, and subgraph listing, a set intersection operator returns common vertices between any two given sets of vertices in data graphs. It is therefore very important to accelerate the set intersection, which will benefit a bunch of tasks that take it as a built-in block. Existing works on the set intersection usually followed the merge intersection or galloping-search framework, and most optimization research focused on how to leverage the SIMD hardware instructions. In this paper, we propose a novel multi-level set intersection framework, namely hierarchical set partitioning and join (HERO), by using our well-designed set intersection bitmap tree (SIB-tree) index, which is independent of SIMD instructions and completely orthogonal to the merge intersection framework. We recursively decompose the set intersection task into small-sized subtasks and solve each subtask using bitmap and boolean AND operations. To sufficiently achieve the acceleration brought by our proposed intersection approach, we formulate a graph reordering problem, prove its NP-hardness, and then develop a heuristic algorithm to tackle this problem. Extensive experiments on real-world graphs have been conducted to confirm the efficiency and effectiveness of our HERO approach. The speedup over classic merge intersection achieves up to 188x and 176x for triangle counting and maximal clique enumeration, respectively.
Förderung
- Natural Science Foundation
- National Natural Science Foundation of China
- Shanghai Science and Technology Innovation Action Plan
Zitieren
APA
Yang, B., Zheng, W., Lian, X., Cai, Y., & Wang, X. S. (2024). HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs. Proceedings of the ACM on Management of Data, 2(1), 1-25. https://doi.org/10.1145/3639284
Vancouver
Yang B, Zheng W, Lian X, Cai Y, Wang XS. HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs. Proceedings of the ACM on Management of Data. 2024;2(1):1-25. doi:10.1145/3639284
BibTeX
@article{Yang2024,
author = {Yang, Boyu and Zheng, Weiguo and Lian, Xiang and Cai, Yuzheng and Wang, X. Sean},
title = {HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {1},
pages = {1--25},
doi = {10.1145/3639284}
}
EUVIMED