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.00019485934
Overall Rank: 382 | 97.44%
DOI: 10.1145/1807167.1807181

Incoming Non-self Citations Over Time

Authors

1. Fang Wei (University of Freiburg)

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
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
1,252	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011336944
1,340	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00010973645
1,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.0001090624
1,426	On k-skip Shortest Paths	2011	SIGMOD	0.00010710481
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010163696
1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.9953879e-05
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9875545e-05
2,188	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8874739e-05
2,604	K-Reach: Who is in Your Small World	2012	VLDB	8.2302549e-05
2,943	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.8314485e-05
3,661	On Querying Historical Evolving Graph Sequences	2011	VLDB	7.1198662e-05
3,687	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0955331e-05
3,920	Effective Caching of Shortest Paths for Location-Based Services	2012	SIGMOD	6.9252611e-05
3,934	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.9172713e-05
4,488	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.5781787e-05
4,915	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.356048e-05
5,101	Relational Approach for Shortest Path Discovery over Large Graphs	2012	VLDB	6.2732849e-05
5,703	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0303375e-05
5,754	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	6.0058421e-05
5,803	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.9893561e-05
5,896	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.9555883e-05
6,107	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.8852347e-05
6,988	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6274541e-05
7,075	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6064033e-05
7,302	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.5602499e-05
7,377	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.5395908e-05
8,042	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.4014499e-05
8,063	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	5.3954994e-05
9,166	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2148514e-05
10,564	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.9793485e-05
11,449	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.9793485e-05
11,600	Efficient kNN Search in Public Transportation Networks	2024	VLDB	4.9793485e-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.

Rank	Cited Paper	Year	Venue	Pagerank
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022490994
294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021927874
330	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00020838159
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017972038
774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014083518
10,054	Tractable Database Design through Bounded Treewidth	2006	PODS	5.087795e-05

Semantically Similar Papers

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