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)
Incoming Non-self Citations Over Time
Authors
- 1. Jingyi Song (University of New South Wales)
- 2. Dong Wen (University of New South Wales)
- 3. Lantian Xu (University of Technology Sydney)
- 4. Lu Qin (University of Technology Sydney)
- 5. Wenjie Zhang (University of New South Wales)
- 6. Xuemin Lin (Shanghai Jiao Tong University)
BibTeX Citation
@inproceedings{song_sigmod24,
title = {{On Querying Historical Connectivity in Temporal Graphs}},
author = {Song, Jingyi and Wen, Dong and Xu, Lantian and Qin, Lu and Zhang, Wenjie and Lin, Xuemin},
series = {{SIGMOD} '24},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3654960},
url = {https://dl.acm.org/doi/10.1145/3654960},
year = {2024}
}
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 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,266 | Maintaining Biconnected Components in Streaming Graphs | 2026 | SIGMOD | 5.093636e-05 |
| 10,283 | Querying Cohesive Subgraphs in Temporal Graphs | 2026 | SIGMOD | 5.093636e-05 |
| 10,424 | ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks | 2026 | SIGMOD | 5.093636e-05 |
| 10,528 | Effective Durable Community Search in Large Temporal Graph | 2026 | VLDB | 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
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.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,635 | Scalable Time-Range k-Core Query on Temporal Graphs | 2023 | VLDB |
| 2 | 10,520 | Efficient Temporal Subgraph Management: A New Interval Index | 2026 | VLDB |
| 3 | 8,812 | On More Efficiently and Versatilely Querying Historical k-Cores | 2025 | VLDB |
| 4 | 8,149 | Efficient Index for Temporal Core Queries over Bipartite Graphs | 2024 | VLDB |
| 5 | 8,718 | Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation | 2024 | VLDB |
| 6 | 5,044 | Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs | 2021 | VLDB |
| 7 | 3,312 | On Querying Historical K-Cores | 2021 | VLDB |
| 8 | 11,198 | Constant-time Connectivity Querying in Dynamic Graphs | 2024 | SIGMOD |
| 9 | 10,283 | Querying Cohesive Subgraphs in Temporal Graphs | 2026 | SIGMOD |
| 10 | 3,836 | On Querying Connected Components in Large Temporal Graphs | 2023 | SIGMOD |