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.9605343e-05
Overall Rank: 11,616 | 22.14%
DOI: 10.14778/3654621.3654636
PDF: Download (CC BY-NC-ND 4.0)

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.0012089097
306	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021533151
358	Regular Path Queries with Constraints	1997	PODS	0.00020030407
536	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016738841
942	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012936571
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,272	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.7108429e-05
2,541	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3021057e-05
2,744	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.0484475e-05
3,530	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2070034e-05
4,027	2SCENT: An Efficient Algorithm for Enumerating All Simple Temporal Cycles	2018	VLDB	6.8324914e-05
4,658	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.468776e-05
5,026	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.2965202e-05
5,073	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.2738154e-05
5,133	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2458323e-05
6,061	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.8831543e-05
6,192	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8377174e-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,483	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS
3	2,272	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD
4	719	Querying Graph Databases	2013	PODS
5	1,474	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
6	5,122	Querying Graph Patterns	2011	PODS
7	11,941	Answering Regular Path Queries through Exemplars	2022	VLDB
8	5,133	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS
9	3,530	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD
10	1,592	Finding Regular Simple Paths in Graph Databases	1989	VLDB