Efficiently Answering Regular Simple Path Queries on Large Labeled Networks

Summary: Introduces ARRIVAL, a random-walk sampling method for RSP queries on large labeled graphs. Delivers theoretical guarantees of quality; ~100x faster than baselines on billion-scale graphs with ~95% accuracy for SPARQL/Cypher-like queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5695
Venue: SIGMOD
Year: 2019
Pagerank: 6.3676619e-05
Overall Rank: 4,191 | 70.88%
DOI: 10.1145/3299869.3319882

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,832	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.048358e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
7,430	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7275494e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-05
8,257	DuckPGQ: Efficient Property Graph Queries in an analytical RDBMS	2023	CIDR	4.5437589e-05
9,483	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3300131e-05
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3212967e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
10,342	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.1905499e-05
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05
11,387	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
2,345	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	8.9933611e-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
4,276	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2884651e-05
5,435	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5074113e-05
5,739	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.3454732e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
10,916	Distinct Shortest Walk Enumeration for RPQs	2024	PODS	4.1905499e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-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
1,445	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011937596
2,832	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.048358e-05
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
11,387	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1905499e-05
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05