I/O-Efficient Butterfly Counting at Scale
Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-27
DOI: 10.1145/3588714 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Zhibin Wang und 5 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: Leading-edge Technology Program of Jiangsu NSF, NSFC, National Key R&D Program of China.
Abstract (Originalsprache)
Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of the kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to "witness" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ømega(|E|2/MB) of a witnessing algorithm, and give a new bound of Ømega(min(|E|2/MB, |E|/|V| √M B)). We further develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we make efforts to parallelize IOBufs to further improve the performance and scalability. We show in the experiment that IOBufs significantly outperforms the state-of-the-art algorithms EMRC and BFC-EM. In addition, IOBufs can scale to conducting butterfly counting on the Clueweb graph with 37 billion edges and quintillions (10^18 ) of butterflies.
Förderung
- Leading-edge Technology Program of Jiangsu NSF
- NSFC
- National Key R&D Program of China
Zitieren
APA
Wang, Z., Lai, L., Liu, Y., Shui, B., Tian, C., & Zhong, S. (2023). I/O-Efficient Butterfly Counting at Scale. Proceedings of the ACM on Management of Data, 1(1), 1-27. https://doi.org/10.1145/3588714
Vancouver
Wang Z, Lai L, Liu Y, Shui B, Tian C, Zhong S. I/O-Efficient Butterfly Counting at Scale. Proceedings of the ACM on Management of Data. 2023;1(1):1-27. doi:10.1145/3588714
BibTeX
@article{Wang2023,
author = {Wang, Zhibin and Lai, Longbin and Liu, Yixue and Shui, Bing and Tian, Chen and Zhong, Sheng},
title = {I/O-Efficient Butterfly Counting at Scale},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {1},
pages = {1--27},
doi = {10.1145/3588714}
}
EUVIMED