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
ha25f2ec99edd3c11
Venue
SIGMOD
Year
2010
Pagerank
0.00019655871
Overall Rank
376 | 97.49%
DOI
10.1145/1807167.1807181
Incoming Non-self Citations Over Time
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 34 of 34 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
192
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013
SIGMOD
0.00025740385
1,250
A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012
SIGMOD
0.00011325987
1,303
Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014
VLDB
0.00011089258
1,346
An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018
VLDB
0.00010949128
1,430
On k-skip Shortest Paths 2011
SIGMOD
0.00010676829
1,577
Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014
VLDB
0.00010155939
1,581
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018
SIGMOD
0.00010151896
1,653
IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013
VLDB
9.9588776e-05
2,201
Scaling Distance Labeling on Small-World Networks 2019
SIGMOD
8.8626226e-05
2,617
K-Reach: Who is in Your Small World 2012
VLDB
8.2001569e-05
2,794
P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021
SIGMOD
7.987154e-05
3,665
On Querying Historical Evolving Graph Sequences 2011
VLDB
7.0996773e-05
3,676
Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022
SIGMOD
7.0882436e-05
3,933
Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012
SIGMOD
6.9003202e-05
3,935
Effective Caching of Shortest Paths for Location-Based Services 2012
SIGMOD
6.8990945e-05
4,214
Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020
SIGMOD
6.7186746e-05
4,938
Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013
VLDB
6.3327465e-05
5,115
Relational Approach for Shortest Path Discovery over Large Graphs 2012
VLDB
6.2559695e-05
5,409
Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022
VLDB
6.1320768e-05
5,699
Hub Labeling for Shortest Path Counting 2020
SIGMOD
6.0139119e-05
5,768
An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019
VLDB
5.9831541e-05
5,893
Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021
SIGMOD
5.9394451e-05
6,073
Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020
SIGMOD
5.8780393e-05
7,008
An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021
VLDB
5.6061911e-05
7,031
Exact Top-k Nearest Keyword Search in Large Networks 2015
SIGMOD
5.6000241e-05
7,323
BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022
SIGMOD
5.5392408e-05
7,399
Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022
VLDB
5.5186598e-05
8,067
Adaptive Optimizations of Recursive Queries in Teradata 2012
SIGMOD
5.3810658e-05
8,085
Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019
VLDB
5.3751128e-05
9,200
Planting Trees for scalable and efficient Canonical Hub Labeling 2020
VLDB
5.1951474e-05
10,414
Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs 2027
SIGMOD
4.9605343e-05
10,638
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026
SIGMOD
4.9605343e-05
11,507
A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025
VLDB
4.9605343e-05
11,653
Efficient kNN Search in Public Transportation Networks 2024
VLDB
4.9605343e-05
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.
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
5,026
Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021
VLDB
2
5,893
Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021
SIGMOD
3
6,997
A Scalable Index for Top-k Subtree Similarity Queries 2019
SIGMOD
4
9,334
TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database 2023
SIGMOD
5
779
Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008
SIGMOD
6
7,399
Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022
VLDB
7
8,684
Top-K Nearest Keyword Search on Large Graphs 2013
VLDB
8
5,409
Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022
VLDB
9
356
On Graph Query Optimization in Large Networks 2010
VLDB
10
4,125
Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016
SIGMOD