DBScholar

Back to papers

TEDI: Efficient Shortest Path Query Answering on Graphs

Summary: TEDI uses tree decomposition to store and query shortest paths in graph bags. Bottom-up traversal over the decomposition enables efficient path queries, yielding smaller index, faster construction, and rapid answers for arbitrary S-T queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4298
Venue
SIGMOD
Year
2010
Pagerank
0.00019937972
Overall Rank
370 | 97.47%
DOI
10.1145/1807167.1807181

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{wei_sigmod10,
        title = {{TEDI: Efficient Shortest Path Query Answering on Graphs}},
        author = {Wei, Fang},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807181},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807181},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
195 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025813775
1,232 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00011566372
1,309 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00011210911
1,339 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00011112799
1,386 On k-skip Shortest Paths 2011 SIGMOD 0.00010950754
1,553 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.0001037809
1,613 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 0.00010216983
1,622 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010201102
2,152 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 9.0778596e-05
2,575 K-Reach: Who is in Your Small World 2012 VLDB 8.3982298e-05
2,871 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 8.0110616e-05
3,594 On Querying Historical Evolving Graph Sequences 2011 VLDB 7.2736453e-05
3,612 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.2579119e-05
3,834 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 7.0841464e-05
3,857 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD 7.0678455e-05
4,403 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7229209e-05
4,813 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.4974292e-05
4,977 Relational Approach for Shortest Path Discovery over Large Graphs 2012 VLDB 6.4166233e-05
5,571 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.1686653e-05
5,678 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1246854e-05
5,784 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 6.0896788e-05
5,890 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB 6.0496722e-05
5,987 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 6.0183678e-05
6,844 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.7566172e-05
6,940 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.7331991e-05
7,158 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.6858492e-05
7,226 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.6667372e-05
7,891 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 5.5211516e-05
7,976 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.5152959e-05
9,003 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.3345443e-05
10,366 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 5.093636e-05
11,097 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 5.093636e-05
11,272 Efficient kNN Search in Public Transportation Networks 2024 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank Cited Paper Year Venue Pagerank
269 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022786599
272 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022695855
282 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.0002242162
322 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00021275303
444 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00018350865
746 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00014402233
9,864 Tractable Database Design through Bounded Treewidth 2006 PODS 5.2045536e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,044 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB
2 5,784 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD
3 6,832 A Scalable Index for Top-k Subtree Similarity Queries 2019 SIGMOD
4 9,131 TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database 2023 SIGMOD
5 746 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD
6 7,226 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB
7 8,493 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB
8 5,678 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB
9 352 On Graph Query Optimization in Large Networks 2010 VLDB
10 4,289 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD