EUVIMEDEUVIMED entdecken
Crossref

I/O-Efficient Butterfly Counting at Scale

Zhibin Wang, Longbin Lai, Yixue Liu, Bing Shui, Chen Tian, Sheng Zhong

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →