Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs

Summary: Proposes Edge-Disjoint Partitioning (EDP) for Edge-Constrained Shortest Path (ECSP) on dynamic, labeled graphs, with a label-driven index and a traversal that exploits ECSP answer regularities. On-demand sub-paths per partition are cached and stitched across partitions; updates invalidate affected entries, delivering up to 10^4× faster ECSP queries on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5124
Venue: SIGMOD
Year: 2016
Pagerank: 5.9573154e-05
Overall Rank: 4,745 | 67.00%
DOI: 10.1145/2882903.2882933

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
7,897	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	4.6230399e-05
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3047774e-05
10,516	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	4.1945683e-05
10,666	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023310419
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
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
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
8,256	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.5490743e-05
11,038	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.1945683e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
3,862	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	6.687769e-05
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837
7,428	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7320892e-05
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362