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: he5b5d0f73a6ec09c
Venue: VLDB
Year: 2024
Pagerank: 4.9793485e-05
Overall Rank: 11,561 | 22.28%
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.0012092602
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.0002159111
356	Regular Path Queries with Constraints	1997	PODS	0.00020103855
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
937	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012977594
2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,257	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.7434588e-05
2,534	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3335732e-05
2,734	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.0789676e-05
3,523	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2343247e-05
4,009	2SCENT: An Efficient Algorithm for Enumerating All Simple Temporal Cycles	2018	VLDB	6.8584055e-05
4,634	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.4933103e-05
5,000	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3202341e-05
5,050	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2976106e-05
5,109	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2695208e-05
6,045	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.9054678e-05
6,177	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8598586e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
2	3,474	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS
3	2,257	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD
4	719	Querying Graph Databases	2013	PODS
5	1,468	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
6	5,096	Querying Graph Patterns	2011	PODS
7	11,891	Answering Regular Path Queries through Exemplars	2022	VLDB
8	5,109	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS
9	3,523	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD
10	1,597	Finding Regular Simple Paths in Graph Databases	1989	VLDB