DBScholar

Back to papers

Relational Approach for Shortest Path Discovery over Large Graphs

Summary: Recasts disk-based graph search as relational FEM—frontier selection, expansion, and merge—using SQL window functions and MERGE. Bidirectional set-Dijkstra plus SegTable indexing accelerates shortest-path discovery with scalable RDB execution. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h95faf2456d1083bc
Venue
VLDB
Year
2012
Pagerank
6.2559695e-05
Overall Rank
5,115 | 65.72%
DOI
10.14778/2095686.2095694

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{gao_vldb12,
        title = {{Relational Approach for Shortest Path Discovery over Large Graphs}},
        author = {Gao, Jun and Jin, Ruoming and Zhou, Jiashuai and Yu, Jeffrey Xu and Jiang, Xiao and Wang, Tengjiao},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {4},
        pages = {358--369},
        doi = {10.14778/2095686.2095694},
        url = {https://doi.org/10.14778/2095686.2095694},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
3,805 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 6.99039e-05
4,451 GRFusion: Graphs as First-Class Citizens in Main-Memory Relational Database Systems 2018 SIGMOD 6.5782534e-05
4,624 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.4807585e-05
4,658 Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice 2020 VLDB 6.468776e-05
4,938 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.3327465e-05
5,409 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1320768e-05
6,862 Towards Unified Ad-hoc Data Processing 2014 SIGMOD 5.6458401e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank Cited Paper Year Venue Pagerank
141 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029191386
331 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00020800828
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019655871
544 ERACER: A Database Approach for Statistical Inference and Data Cleaning 2010 SIGMOD 0.00016584014
643 Finding Maximal Cliques in Massive Networks by H*-graph 2010 SIGMOD 0.00015219469
963 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00012805146
1,148 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011777466
3,150 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.5754686e-05
3,656 Implementing A Scalable XML Publish/Subscribe System Using Relational Database Systems 2004 SIGMOD 7.1122914e-05
4,732 DTD-Directed Publishing with Attribute Translation Grammars 2002 VLDB 6.4311491e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB
2 6,501 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB
3 5,409 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB
4 8,399 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB
5 3,030 Graph-Theoretic Methods In Database Theory 1990 PODS
6 1,505 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD
7 993 Path Oracles for Spatial Networks 2009 VLDB
8 10,937 Nav-Index: A High-Performance, Adaptive Index for Shortest Path Queries in RDBMS 2026 VLDB
9 4,125 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD
10 356 On Graph Query Optimization in Large Networks 2010 VLDB