Database Paper Browser

Back to papers

On Querying Historical Connectivity in Temporal Graphs

Summary: Historical connectivity in evolving temporal graphs: new forest-based index for windowed reachability, replacing costly dynamic two-hop covers. Queries reduce to connectivity checks in the forest; incremental forest maintenance also supports sliding-window connectivity efficiently. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID
6921
Venue
SIGMOD
Year
2024
Pagerank
4.9720132e-05
Overall Rank
6,657 | 53.69%
DOI
10.1145/3654960

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank Citing Paper Year Venue Pagerank
9,641 An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs 2025 SIGMOD 4.3109001e-05
10,135 ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks 2026 SIGMOD 4.1945683e-05
10,240 Effective Durable Community Search in Large Temporal Graph 2026 VLDB 4.1945683e-05
10,383 Minimum Spanning Tree Maintenance in Dynamic Graphs 2025 SIGMOD 4.1945683e-05
10,547 On More Efficiently and Versatilely Querying Historical k-Cores 2025 VLDB 4.1945683e-05
10,985 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank Cited Paper Year Venue Pagerank
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
1,777 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.00010589591
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
2,826 Regular Path Query Evaluation on Streaming Graphs 2020 SIGMOD 8.056119e-05
3,063 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 7.6321424e-05
3,146 Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs 2022 VLDB 7.477231e-05
4,139 On Querying Historical K-Cores 2021 VLDB 6.415046e-05
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1506256e-05
4,970 On Querying Connected Components in Large Temporal Graphs 2023 SIGMOD 5.7945079e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,042 HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs 2023 SIGMOD 4.4039656e-05
7,341 Scalable Time-Range k-Core Query on Temporal Graphs 2023 VLDB 4.7576413e-05
10,232 Efficient Temporal Subgraph Management: A New Interval Index 2026 VLDB 4.1945683e-05
10,547 On More Efficiently and Versatilely Querying Historical k-Cores 2025 VLDB 4.1945683e-05
11,042 Efficient Index for Temporal Core Queries over Bipartite Graphs 2024 VLDB 4.1945683e-05
11,044 Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation 2024 VLDB 4.1945683e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
4,139 On Querying Historical K-Cores 2021 VLDB 6.415046e-05
10,985 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1945683e-05
4,970 On Querying Connected Components in Large Temporal Graphs 2023 SIGMOD 5.7945079e-05