DBScholar

Back to papers

Maintaining Biconnected Components in Streaming Graphs

Summary: An index compresses BCCs across sliding-window subwindows, avoiding explicit deletion maintenance and discarding expired-edge regions in O(1) time. Insertions progressively update the index via tree-edge rotations, achieving optimal space and strong empirical speedups. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID
7457
Venue
SIGMOD
Year
2026
Pagerank
5.093636e-05
Overall Rank
10,266 | 29.57%
DOI
10.1145/3802084

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

BibTeX Citation

@inproceedings{lu_sigmod26,
        title = {{Maintaining Biconnected Components in Streaming Graphs}},
        author = {Lu, Zhao and Wen, Dong and Li, Wentao and Lin, Xuemin and Zhang, Wenjie},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3802084},
        url = {https://dl.acm.org/doi/10.1145/3802084},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1,513 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010530872
2,635 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 8.3200595e-05
2,798 Incremental Graph Computations: Doable and Undoable 2017 SIGMOD 8.1129891e-05
3,065 Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees 2014 VLDB 7.7989716e-05
3,068 RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s 2021 SIGMOD 7.7939351e-05
3,312 On Querying Historical K-Cores 2021 VLDB 7.5309892e-05
3,836 On Querying Connected Components in Large Temporal Graphs 2023 SIGMOD 7.0827068e-05
4,443 Incrementalizing Graph Algorithms 2021 SIGMOD 6.7004839e-05
5,483 DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows 2022 SIGMOD 6.2019677e-05
6,075 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 5.9853864e-05
6,868 Incremental Sliding Window Connectivity over Streaming Graphs 2024 VLDB 5.7501594e-05
6,937 Querying Structural Diversity in Streaming Graphs 2024 VLDB 5.7348103e-05
8,502 MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs 2024 SIGMOD 5.4132367e-05
8,504 Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries 2024 VLDB 5.4132367e-05
8,657 An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs 2025 SIGMOD 5.3907647e-05
8,812 On More Efficiently and Versatilely Querying Historical k-Cores 2025 VLDB 5.3652966e-05
10,411 Triangle Counting in Hypergraph Streams: A Complete and Practical Approach 2026 SIGMOD 5.093636e-05
10,671 Minimum Spanning Tree Maintenance in Dynamic Graphs 2025 SIGMOD 5.093636e-05
11,198 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Semantically Similar Papers