EUVIMEDOpdag EUVIMED
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 · 2026-05-18 · 4 (3) · 1-25

DOI: 10.1145/3802084 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Zhao Lu and 4 co-authors. 71 references. Funded by: ARC, NSFC, Guangdong Basic and Applied Basic Research Foundation.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Funding

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

Cite

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}
}
Start for free →