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: 13598
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,225 | 22.99%
DOI: 10.14778/3654621.3654636

Incoming Non-self Citations Over Time

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

Authors

1. Qi Liang (Guangdong University of Technology)
2. Dian Ouyang (Guangdong University of Technology)
3. Fan Zhang (Guangdong University of Technology)
4. Jianye Yang (Guangdong University of Technology; Peng Cheng Laboratory)
5. Xuemin Lin (Shanghai Jiao Tong University)
6. Zhihong Tian (Guangdong University of Technology)

BibTeX Citation

@article{liang_vldb24,
        title = {{Efficient Regular Simple Path Queries under Transitive Restricted Expressions}},
        author = {Liang, Qi and Ouyang, Dian and Zhang, Fan and Yang, Jianye and Lin, Xuemin and Tian, Zhihong},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {7},
        pages = {1710--1722},
        doi = {10.14778/3654621.3654636},
        url = {https://doi.org/10.14778/3654621.3654636},
        year = {2024}
}

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
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
530	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001709169
927	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00013161079
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,209	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.9437338e-05
2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.5090456e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,473	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.3864987e-05
3,955	2SCENT: An Efficient Algorithm for Enumerating All Simple Temporal Cycles	2018	VLDB	6.9950293e-05
4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.6355948e-05
4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.4193234e-05
4,981	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.4127882e-05
5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3883109e-05
5,938	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	6.0343238e-05
6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.824568e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
2	3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS
3	2,209	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD
4	747	Querying Graph Databases	2013	PODS
5	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
6	4,986	Querying Graph Patterns	2011	PODS
7	11,583	Answering Regular Path Queries through Exemplars	2022	VLDB
8	4,981	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS
9	3,473	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD
10	1,658	Finding Regular Simple Paths in Graph Databases	1989	VLDB