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
10672
Venue
VLDB
Year
2012
Pagerank
6.4166233e-05
Overall Rank
4,977 | 65.86%
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,872 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 7.0580243e-05
4,340 GRFusion: Graphs as First-Class Citizens in Main-Memory Relational Database Systems 2018 SIGMOD 6.7539375e-05
4,541 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.6397712e-05
4,551 Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice 2020 VLDB 6.6355948e-05
4,813 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.4974292e-05
5,678 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1246854e-05
6,714 Towards Unified Ad-hoc Data Processing 2014 SIGMOD 5.7959651e-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
137 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00029877792
322 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00021275303
370 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019937972
549 ERACER: A Database Approach for Statistical Inference and Data Cleaning 2010 SIGMOD 0.00016692839
674 Finding Maximal Cliques in Massive Networks by H*-graph 2010 SIGMOD 0.00015081844
945 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00013066956
1,128 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.0001206219
3,119 GConnect: A Connectivity Index for Massive Disk-Resident Graphs 2009 VLDB 7.7370163e-05
3,567 Implementing A Scalable XML Publish/Subscribe System Using Relational Database Systems 2004 SIGMOD 7.302431e-05
4,619 DTD-Directed Publishing with Attribute Translation Grammars 2002 VLDB 6.6033756e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,854 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD
2 6,387 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB
3 37 DISCOVER: Keyword Search in Relational Databases 2002 VLDB
4 5,678 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB
5 8,245 The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis 2016 VLDB
6 2,957 Graph-Theoretic Methods In Database Theory 1990 PODS
7 1,555 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD
8 968 Path Oracles for Spatial Networks 2009 VLDB
9 4,289 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD
10 352 On Graph Query Optimization in Large Networks 2010 VLDB