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: 5949
Venue: SIGMOD
Year: 2020
Pagerank: 8.048358e-05
Overall Rank: 2,832 | 80.32%
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,310	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.2370328e-05
6,391	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0780425e-05
6,479	EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs	2023	SIGMOD	5.0405101e-05
6,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-05
7,212	Space-Efficient Random Walks on Streaming Graphs	2023	VLDB	4.7943898e-05
7,439	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	4.7256836e-05
7,581	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.701915e-05
7,629	Incremental Sliding Window Connectivity over Streaming Graphs	2024	VLDB	4.6883161e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-05
8,459	D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks	2024	VLDB	4.5008938e-05
8,571	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	4.4887087e-05
8,982	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.413691e-05
9,483	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3300131e-05
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
9,953	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB	4.2360271e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
10,135	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	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 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.00072660894
191	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00035714897
287	Storm @Twitter	2014	SIGMOD	0.00028917909
327	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027312381
364	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00025657601
530	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020823189
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
727	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017462279
822	Twitter Heron: Stream Processing at Scale	2015	SIGMOD	0.00016226851
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00014967208
1,040	Querying Graph Databases	2013	PODS	0.00014483577
1,392	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012224015
3,231	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.3333516e-05
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3676619e-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
7,280	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	4.7718173e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,527	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4573655e-05
9,556	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	4.3212967e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3676619e-05
11,387	Answering Regular Path Queries through Exemplars	2022	VLDB	4.1905499e-05
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
1,040	Querying Graph Databases	2013	PODS	0.00014483577
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05
9,483	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	4.3300131e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-05