Regular Path Query Evaluation on Streaming Graphs

Summary: Proposes deterministic, uniform persistent RPQ evaluation for streaming graphs, handling both arbitrary and simple path semantics. Experiments on real and synthetic streams show scalable throughput and efficient RPQ answering in real workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5948
Venue: SIGMOD
Year: 2020
Pagerank: 8.056119e-05
Overall Rank: 2,826 | 80.35%
DOI: 10.1145/3318464.3389733

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,306	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.2437997e-05
6,395	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0829204e-05
6,485	EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs	2023	SIGMOD	5.0453531e-05
6,657	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9720132e-05
7,212	Space-Efficient Random Walks on Streaming Graphs	2023	VLDB	4.7989929e-05
7,441	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	4.7302202e-05
7,576	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.7064285e-05
7,627	Incremental Sliding Window Connectivity over Streaming Graphs	2024	VLDB	4.6928167e-05
8,170	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5697385e-05
8,463	D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks	2024	VLDB	4.5052127e-05
8,574	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	4.4930153e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
9,481	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3341665e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
9,954	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB	4.2400894e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05
10,135	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	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 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
191	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00035738595
288	Storm @Twitter	2014	SIGMOD	0.00028939871
331	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027214222
363	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025715157
536	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020722862
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
733	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017460741
824	Twitter Heron: Stream Processing at Scale	2015	SIGMOD	0.0001623129
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.0001497475
1,037	Querying Graph Databases	2013	PODS	0.00014502493
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
3,228	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.3405281e-05
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3735885e-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
7,282	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	4.776631e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,517	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4626107e-05
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3254416e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3735885e-05
11,385	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1945683e-05
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
1,037	Querying Graph Databases	2013	PODS	0.00014502493
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
9,481	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3341665e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05
8,170	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5697385e-05