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: h2671dda84e0ea2f2
Venue: SIGMOD
Year: 2020
Pagerank: 8.7434588e-05
Overall Rank: 2,257 | 84.83%
DOI: 10.1145/3318464.3389733

Incoming Non-self Citations Over Time

Authors

1. Anil Pacaci (University of Waterloo)
2. Angela Bonifati (Claude Bernard Lyon 1 University)
3. M. Tamer Özsu (University of Waterloo)

BibTeX Citation

@inproceedings{pacaci_sigmod20,
        title = {{Regular Path Query Evaluation on Streaming Graphs}},
        author = {Pacaci, Anil and Bonifati, Angela and Özsu, M. Tamer},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389733},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389733},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,831	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.9602632e-05
5,984	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.926237e-05
6,200	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	5.8510904e-05
6,324	EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs	2023	SIGMOD	5.8137796e-05
7,013	Incremental Sliding Window Connectivity over Streaming Graphs	2024	VLDB	5.6211413e-05
7,076	Querying Structural Diversity in Streaming Graphs	2024	VLDB	5.6061365e-05
7,302	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.5602499e-05
7,405	Space-Efficient Random Walks on Streaming Graphs	2023	VLDB	5.5354654e-05
8,211	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.3772821e-05
8,623	D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks	2024	VLDB	5.3009314e-05
8,669	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	5.2917782e-05
8,813	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	5.2711766e-05
9,150	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.21801e-05
9,805	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1257999e-05
10,330	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB	5.0312167e-05
10,431	cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries	2026	SIGMOD	4.9793485e-05
10,561	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.9793485e-05
10,613	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	4.9793485e-05
11,074	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.9793485e-05
11,561	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.9793485e-05
11,891	Answering Regular Path Queries through Exemplars	2022	VLDB	4.9793485e-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
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030427614
231	Storm @Twitter	2014	SIGMOD	0.00023841089
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.0002159111
387	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00019426275
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
606	Twitter Heron: Stream Processing at Scale	2015	SIGMOD	0.00015635133
693	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014734389
719	Querying Graph Databases	2013	PODS	0.00014529156
860	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013406849
937	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012977594
2,851	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9419904e-05
3,155	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.5858519e-05
3,420	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	7.3147525e-05
3,523	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2343247e-05
5,109	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2695208e-05
7,462	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	5.521211e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,557	Representing Paths in Graph Database Pattern Matching	2023	VLDB
2	9,140	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD
3	3,523	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD
4	11,891	Answering Regular Path Queries through Exemplars	2022	VLDB
5	356	Regular Path Queries with Constraints	1997	PODS
6	719	Querying Graph Databases	2013	PODS
7	11,561	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB
8	8,669	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD
9	10,561	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD
10	8,211	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB