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: 5694
Venue: SIGMOD
Year: 2019
Pagerank: 6.3735885e-05
Overall Rank: 4,191 | 70.85%
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,826	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.056119e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
7,428	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7320892e-05
8,170	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5697385e-05
8,276	DuckPGQ: Efficient Property Graph Queries in an analytical RDBMS	2023	CIDR	4.5439811e-05
9,481	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3341665e-05
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3254416e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05
10,330	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.1945683e-05
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
11,385	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1945683e-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
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
2,342	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.0015589e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
4,280	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2948356e-05
5,424	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	5.5126983e-05
5,730	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.3506029e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
10,912	Distinct Shortest Walk Enumeration for RPQs	2024	PODS	4.1945683e-05
8,170	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5697385e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
1,444	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00011946075
2,826	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.056119e-05
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
11,385	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1945683e-05
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05