TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph

Summary: TF-label proposes a topological folding labeling scheme for reachability in large graphs; folds the graph in half to shrink labels. Efficient construction and optimization; scalable index-building yield faster reachability queries than state-of-the-art methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4696
Venue: SIGMOD
Year: 2013
Pagerank: 0.00010227906
Overall Rank: 1,879 | 86.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,021	Path Problems in Temporal Graphs	2014	VLDB	0.00014608331
1,392	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012224015
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
2,916	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.9062736e-05
3,155	Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs	2022	VLDB	7.4700348e-05
3,221	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3541078e-05
3,676	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8500097e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1452192e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
5,488	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.4798261e-05
6,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
7,595	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.6980168e-05
7,714	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6651585e-05
8,666	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	4.467539e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.3997447e-05
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
9,897	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	4.2559233e-05
10,988	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1905499e-05
11,193	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
106	Truss Decomposition in Massive Networks	2012	VLDB	0.00048373761
255	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030342925
280	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029092277
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027077424
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023592024
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
727	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017462279
1,551	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011395294
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
2,762	K-Reach: Who is in Your Small World	2012	VLDB	8.1614818e-05
3,130	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5054361e-05
4,070	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4739921e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
1,822	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010404349
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
7,430	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7275494e-05
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1452192e-05
3,676	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8500097e-05
2,958	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8126329e-05
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392