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.2732849e-05
Overall Rank
5,101 | 65.71%
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,798 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 7.0161889e-05
4,428 GRFusion: Graphs as First-Class Citizens in Main-Memory Relational Database Systems 2018 SIGMOD 6.603203e-05
4,604 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.505032e-05
4,634 Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice 2020 VLDB 6.4933103e-05
4,915 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.356048e-05
5,803 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 5.9893561e-05
6,840 Towards Unified Ad-hoc Data Processing 2014 SIGMOD 5.6669233e-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.00029294114
330 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00020838159
382 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019485934
547 ERACER: A Database Approach for Statistical Inference and Data Cleaning 2010 SIGMOD 0.00016578131
645 Finding Maximal Cliques in Massive Networks by H*-graph 2010 SIGMOD 0.00015213733
962 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00012820478
1,148 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011809728
3,168 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.5723309e-05
3,646 Implementing A Scalable XML Publish/Subscribe System Using Relational Database Systems 2004 SIGMOD 7.1389574e-05
4,717 DTD-Directed Publishing with Attribute Translation Grammars 2002 VLDB 6.4552474e-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,485 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB
3 5,803 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB
4 8,413 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB
5 3,020 Graph-Theoretic Methods In Database Theory 1990 PODS
6 1,501 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD
7 990 Path Oracles for Spatial Networks 2009 VLDB
8 10,867 Nav-Index: A High-Performance, Adaptive Index for Shortest Path Queries in RDBMS 2026 VLDB
9 4,139 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD
10 355 On Graph Query Optimization in Large Networks 2010 VLDB