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: 13411
Venue: VLDB
Year: 2024
Pagerank: 4.1905499e-05
Overall Rank: 11,017 | 23.44%
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.0019040811
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
1,392	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012224015
2,345	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	8.9933611e-05
2,832	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.048358e-05
2,958	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8126329e-05
3,221	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3541078e-05
3,959	2SCENT: An Efficient Algorithm for Enumerating All Simple Temporal Cycles	2018	VLDB	6.583977e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3676619e-05
4,536	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.099154e-05
5,267	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	5.5930569e-05
5,435	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5074113e-05
5,548	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4445937e-05
6,207	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1519085e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
3,659	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	6.8684407e-05
2,832	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.048358e-05
1,040	Querying Graph Databases	2013	PODS	0.00014483577
1,812	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010458164
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
11,387	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1905499e-05
5,435	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5074113e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3676619e-05
1,445	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011937596