Efficient Regular Simple Path Queries under Transitive Restricted Expressions

Summary: Define transitive restricted expressions (covering >99% of real-world RSPQs) and give an exact framework for reachability and enumeration for them. New reachability tests, candidate pruning, and redundancy elimination achieve near-approximate speeds and up to 100× exact-method speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13410
Venue: VLDB
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 11,014 | 23.38%
DOI: 10.14778/3654621.3654636

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
2,342	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.0015589e-05
2,826	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.056119e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
3,957	2SCENT: An Efficient Algorithm for Enumerating All Simple Temporal Cycles	2018	VLDB	6.5903145e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3735885e-05
4,534	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.1049756e-05
5,259	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	5.5984356e-05
5,424	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5126983e-05
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
6,208	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1568586e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
3,652	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.875313e-05
2,826	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.056119e-05
1,037	Querying Graph Databases	2013	PODS	0.00014502493
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010467069
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
11,385	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1945683e-05
5,424	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5126983e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3735885e-05
1,444	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011946075