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.9769913e-05
Overall Rank
10,490 | 29.50%
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,441 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010638056
2,669 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 8.1492816e-05
2,851 Incremental Graph Computations: Doable and Undoable 2017 SIGMOD 7.9382307e-05
3,109 Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees 2014 VLDB 7.6384672e-05
3,115 RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s 2021 SIGMOD 7.6315625e-05
3,251 On Querying Historical K-Cores 2021 VLDB 7.4903737e-05
3,922 On Querying Connected Components in Large Temporal Graphs 2023 SIGMOD 6.9205122e-05
4,541 Incrementalizing Graph Algorithms 2021 SIGMOD 6.547718e-05
5,613 DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows 2022 SIGMOD 6.0654968e-05
6,205 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 5.8483206e-05
7,014 Incremental Sliding Window Connectivity over Streaming Graphs 2024 VLDB 5.6184803e-05
7,077 Querying Structural Diversity in Streaming Graphs 2024 VLDB 5.6034826e-05
8,677 MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs 2024 SIGMOD 5.2892731e-05
8,679 Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries 2024 VLDB 5.2892731e-05
8,828 An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs 2025 SIGMOD 5.2673158e-05
8,987 On More Efficiently and Versatilely Querying Historical k-Cores 2025 VLDB 5.2424308e-05
10,614 Triangle Counting in Hypergraph Streams: A Complete and Practical Approach 2026 SIGMOD 4.9769913e-05
11,121 Minimum Spanning Tree Maintenance in Dynamic Graphs 2025 SIGMOD 4.9769913e-05
11,546 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.9769913e-05
Previous Page 1 / 1 Next

Semantically Similar Papers