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
h296dfa57b1c9b6d4
Venue
SIGMOD
Year
2026
Pagerank
4.9605343e-05
Overall Rank
10,556 | 29.25%
DOI
10.1145/3802084
PDF
Download (CC BY 4.0)

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,447 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010604169
2,680 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 8.1227558e-05
2,854 Incremental Graph Computations: Doable and Undoable 2017 SIGMOD 7.9179612e-05
3,101 Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees 2014 VLDB 7.6310428e-05
3,123 RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s 2021 SIGMOD 7.6082482e-05
3,170 On Querying Historical K-Cores 2021 VLDB 7.5572564e-05
3,928 On Querying Connected Components in Large Temporal Graphs 2023 SIGMOD 6.9013791e-05
4,557 Incrementalizing Graph Algorithms 2021 SIGMOD 6.5264915e-05
5,625 DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows 2022 SIGMOD 6.0454405e-05
6,209 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 5.8323161e-05
7,032 Incremental Sliding Window Connectivity over Streaming Graphs 2024 VLDB 5.5999021e-05
7,087 Querying Structural Diversity in Streaming Graphs 2024 VLDB 5.5882877e-05
8,536 On More Efficiently and Versatilely Querying Historical k-Cores 2025 VLDB 5.3051047e-05
8,697 MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs 2024 SIGMOD 5.2717835e-05
8,699 Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries 2024 VLDB 5.2717835e-05
8,845 An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs 2025 SIGMOD 5.2498988e-05
10,675 Triangle Counting in Hypergraph Streams: A Complete and Practical Approach 2026 SIGMOD 4.9605343e-05
11,182 Minimum Spanning Tree Maintenance in Dynamic Graphs 2025 SIGMOD 4.9605343e-05
11,595 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Semantically Similar Papers