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.7108429e-05
Overall Rank: 2,272 | 84.78%
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,843	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.9301857e-05
5,995	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.903845e-05
6,209	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	5.8323161e-05
6,339	EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs	2023	SIGMOD	5.7918126e-05
7,032	Incremental Sliding Window Connectivity over Streaming Graphs	2024	VLDB	5.5999021e-05
7,087	Querying Structural Diversity in Streaming Graphs	2024	VLDB	5.5882877e-05
7,323	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.5392408e-05
7,426	Space-Efficient Random Walks on Streaming Graphs	2023	VLDB	5.5145499e-05
8,236	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.3569644e-05
8,649	D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks	2024	VLDB	5.2809021e-05
8,697	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	5.2717835e-05
8,840	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	5.2513168e-05
9,184	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	5.1982941e-05
9,846	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1064323e-05
10,363	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB	5.0122065e-05
10,509	cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries	2026	SIGMOD	4.9605343e-05
10,635	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.9605343e-05
10,685	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	4.9605343e-05
11,144	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.9605343e-05
11,616	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.9605343e-05
11,941	Answering Regular Path Queries through Exemplars	2022	VLDB	4.9605343e-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.00051942573
128	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030317705
233	Storm @Twitter	2014	SIGMOD	0.00023754096
235	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00023701614
306	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021533151
387	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00019360364
536	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016738841
607	Twitter Heron: Stream Processing at Scale	2015	SIGMOD	0.00015577054
694	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014681018
719	Querying Graph Databases	2013	PODS	0.00014493767
854	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013432811
942	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012936571
2,854	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9179612e-05
3,169	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.557345e-05
3,433	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	7.2871281e-05
3,530	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2070034e-05
5,133	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2458323e-05
7,485	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	5.5003667e-05

Semantically Similar Papers

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