Maintaining Biconnected Components in Streaming Graphs
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.
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}
}
EUVIMED