Worst-Case Optimal BGPs on Temporal Graphs

Summary: Introduces a linear-space index and temporal Leapfrog Triejoin for BGPs over interval-valid labeled graphs with time variables and order predicates. Provides worst-case-optimal O(Q*^m log N) evaluation, extending guarantees to snapshot and version queries. (summarized by gpt-5.6-luna on Aug 28 2026)

Paper ID: hf370e4645b11e3cc
Venue: VLDB
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,854 | 27.03%
DOI: 10.14778/3836663.3836681

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Diego Arroyuelo (Millennium Institute Foundational Research on Data; Pontifical Catholic University of Chile)
2. Aidan Hogan (Millennium Institute Foundational Research on Data; Universidad de Chile)
3. Gonzalo Navarro (Millennium Institute Foundational Research on Data; Universidad de Chile)
4. Juan Reutter (Millennium Institute Foundational Research on Data; Pontifical Catholic University of Chile)

BibTeX Citation

@article{arroyuelo_vldb26,
        title = {{Worst-Case Optimal BGPs on Temporal Graphs}},
        author = {Arroyuelo, Diego and Hogan, Aidan and Navarro, Gonzalo and Reutter, Juan},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {11},
        pages = {3174--3187},
        doi = {10.14778/3836663.3836681},
        url = {https://doi.org/10.14778/3836663.3836681},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
419	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.0001854669
712	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014578373
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
1,105	Path Problems in Temporal Graphs	2014	VLDB	0.00011996469
1,128	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00011905274
1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010127607
1,812	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5803973e-05
5,010	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	6.3149028e-05
6,426	Temporal Alignment	2012	SIGMOD	5.7891979e-05
6,955	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	5.6342744e-05
7,367	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.5411636e-05
7,609	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4847975e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,452	Temporal Relationships in Databases	1988	VLDB
2	4,605	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD
3	3,921	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD
4	8,832	On Reporting Durable Patterns in Temporal Proximity Graphs	2024	PODS
5	5,000	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB
6	8,977	On More Efficiently and Versatilely Querying Historical k-Cores	2025	VLDB
7	10,705	Efficient Temporal Subgraph Management: A New Interval Index	2026	VLDB
8	6,200	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD
9	8,318	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB
10	6,767	Scalable Time-Range k-Core Query on Temporal Graphs	2023	VLDB