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: 5125
Venue: SIGMOD
Year: 2016
Pagerank: 6.8841731e-05
Overall Rank: 4,226 | 70.64%
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,059	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	9.3142927e-05
6,504	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.9147772e-05
7,104	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.754502e-05
7,852	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	5.6007152e-05
9,664	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.2956801e-05
10,525	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	5.1725247e-05
10,674	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	5.1725247e-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
431	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018656653
1,252	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011557184

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
736	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.0001459447
1,772	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.8669496e-05
365	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00020126807
8,011	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.5653705e-05
11,041	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.1725247e-05
3,479	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.4546535e-05
1,252	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011557184
7,104	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.754502e-05
7,219	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	5.7244393e-05
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020516762