EUVIMEDEUVIMED entdecken
Crossref

An Efficient Streaming Algorithm for Approximating Graphlet Distributions

Marco Bressan, T-H. Hubert Chan, Qipeng Kuang, Mauro Sozio

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26

DOI: 10.1145/3802010 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Marco Bressan und 3 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: Hong Kong Research Grants Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In recent years, the problem of computing the frequencies of the induced k -vertex subgraphs of a graph, or k-graphlets, has become central. One approach for this problem is to sample k -graphlets randomly. Classic algorithms for k -graphlet sampling require loading the entire graph into main memory, making them impractical for massive graphs. To bypass this limitation, Bourreau et al. (NeurIPS 2024) introduced a streaming algorithm that through nontrivial techniques makes only O (log n ) passes using O ( n log n ) memory. In this work we break their O (log n )-pass bound by giving an algorithm that, for any fixed c > 0, makes O (1/ c ) passes using Õ( n 1+ c ) memory. As a consequence of their lower bound, our algorithm is optimal up to a factor of Õ (n c ) in the memory usage. We use this sampling algorithm to obtain an efficient method of approximating k -graphlet distributions. Experiments on real-world and synthetic graphs show that our algorithm is always at least as good as the one of Bourreau et al., and outperforms it by orders of magnitude on mildly dense graphs.

Förderung

  • Hong Kong Research Grants Council

Zitieren

APA

Bressan, M., Chan, T. H., Kuang, Q., & Sozio, M. (2026). An Efficient Streaming Algorithm for Approximating Graphlet Distributions. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802010

Vancouver

Bressan M, Chan TH, Kuang Q, Sozio M. An Efficient Streaming Algorithm for Approximating Graphlet Distributions. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802010

BibTeX
@article{Bressan2026,
  author = {Bressan, Marco and Chan, T-H. Hubert and Kuang, Qipeng and Sozio, Mauro},
  title = {An Efficient Streaming Algorithm for Approximating Graphlet Distributions},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3802010}
}
Kostenlos starten →