EUVIMEDEUVIMED entdecken
Crossref

Maintaining Biconnected Components in Streaming Graphs

Zhao Lu, Dong Wen, Wentao Li, Xuemin Lin, Wenjie Zhang

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

DOI: 10.1145/3802084 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Zhao Lu und 4 weiteren Autor:innen. Die Arbeit nennt 71 Literaturangaben. Gefördert von: ARC, NSFC, Guangdong Basic and Applied Basic Research Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Biconnected components (BCCs) are fundamental structures in graph analysis, with applications spanning various domains. To support these applications over continuously evolving data, we study the problem of maintaining BCCs in streaming graphs under the widely used sliding-window model. Existing methods suffer from a severe bottleneck in edge deletion, which dominates their practical running time. To overcome this limitation, we design an index that eliminates the need to maintain BCCs under edge deletions. This index compresses all BCCs across sub-windows ending at the current timestamp and achieves optimal space complexity. When an edge expires and is deleted, the portion of the index corresponding to the sub-window containing this edge can be directly discarded in constant time. For edge insertions, we develop a two-step maintenance framework that progressively transforms the outdated index into the updated version through a sequence of tree-edge rotations. Extensive experiments on real-world datasets demonstrate that our approach considerably outperforms state-of-the-art methods.

Förderung

  • ARC
  • NSFC
  • Guangdong Basic and Applied Basic Research Foundation

Zitieren

APA

Lu, Z., Wen, D., Li, W., Lin, X., & Zhang, W. (2026). Maintaining Biconnected Components in Streaming Graphs. Proceedings of the ACM on Management of Data, 4(3), 1-25. https://doi.org/10.1145/3802084

Vancouver

Lu Z, Wen D, Li W, Lin X, Zhang W. Maintaining Biconnected Components in Streaming Graphs. Proceedings of the ACM on Management of Data. 2026;4(3):1-25. doi:10.1145/3802084

BibTeX
@article{Lu2026,
  author = {Lu, Zhao and Wen, Dong and Li, Wentao and Lin, Xuemin and Zhang, Wenjie},
  title = {Maintaining Biconnected Components in Streaming Graphs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--25},
  doi = {10.1145/3802084}
}
Kostenlos starten →