DAG Reduction: Fast Answering Reachability Queries

Summary: Proposes DAG reduction to accelerate reachability queries by shrinking DAGs with transitive reduction (TR) and equivalence reduction (ER). buTR yields the smallest DAG with the same transitive closure; linear-ER compresses further in linear time for scalable reachability on large graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5293
Venue: SIGMOD
Year: 2017
Pagerank: 4.7016964e-05
Overall Rank: 7,596 | 47.16%
DOI: 10.1145/3035918.3035927

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
733	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017460741
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
1,553	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011402871
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
3,120	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5295938e-05
3,127	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5046522e-05
3,671	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8560247e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
880	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015667998
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591