Back to papers
Output-Sensitive Evaluation of Regular Path Queries
Summary: Introduces OSPG, an output-sensitive refinement of the Product Graph for evaluating regular path queries on edge-labeled graphs. Data complexity: O(|E|^{3/2} + min(OUT·√|E|, |V|·|E|)) with OUT the output size; excels when outputs are small or graphs are sparse, and for non-Kleene-star queries tightens to O(|E| + |E|√OUT).
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 1976
- Venue
- PODS
- Year
- 2025
- Pagerank
- 4.2897489e-05
- Overall Rank
- 9,744 | 32.22%
- DOI
-
10.1145/3725242
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 24 of 24 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 690 |
An Analytical Study of Large SPARQL Query Logs |
2018 |
VLDB |
0.00018099792 |
| 789 |
Cypher: An Evolving Query Language for Property Graphs |
2018 |
SIGMOD |
0.00016634256 |
| 1,037 |
Querying Graph Databases |
2013 |
PODS |
0.00014502493 |
| 1,259 |
Aggregation and Ordering in Factorised Databases |
2013 |
VLDB |
0.00012995821 |
| 1,442 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011956109 |
| 1,812 |
Expressive Languages for Path Queries over Graph-Structured Data |
2010 |
PODS |
0.00010467069 |
| 2,212 |
Skew in Parallel Query Processing |
2014 |
PODS |
9.2771827e-05 |
| 2,505 |
Graph Pattern Matching in GQL and SQL/PGQ |
2022 |
SIGMOD |
8.634551e-05 |
| 3,006 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7299363e-05 |
| 3,387 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.1573735e-05 |
| 3,715 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8220943e-05 |
| 3,833 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7173578e-05 |
| 4,708 |
Instance and Output Optimal Parallel Algorithms for Acyclic Joins |
2019 |
PODS |
5.980172e-05 |
| 5,517 |
Representing Paths in Graph Database Pattern Matching |
2023 |
VLDB |
5.4626107e-05 |
| 5,858 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2997454e-05 |
| 5,902 |
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication |
2015 |
PODS |
5.2796864e-05 |
| 5,962 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2536266e-05 |
| 6,647 |
Fast Join Project Query Evaluation using Matrix Multiplication |
2020 |
SIGMOD |
4.9772122e-05 |
| 7,065 |
Fast Matrix Multiplication for Query Processing |
2024 |
PODS |
4.8447515e-05 |
| 7,761 |
Space-Time Tradeoffs for Conjunctive Queries with Access Patterns |
2023 |
PODS |
4.658708e-05 |
| 8,589 |
Output-Optimal Algorithms for Join-Aggregate Queries |
2025 |
PODS |
4.4897014e-05 |
| 8,804 |
Conjunctive Regular Path Queries under Injective Semantics |
2023 |
PODS |
4.4468701e-05 |
| 8,966 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4193184e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 11,385 |
Answering Regular Path Queries through Exemplars |
2022 |
VLDB |
4.1945683e-05 |
| 1,037 |
Querying Graph Databases |
2013 |
PODS |
0.00014502493 |
| 3,652 |
The Complexity of Evaluating Path Expressions in SPARQL |
2012 |
PODS |
6.875313e-05 |
| 2,826 |
Regular Path Query Evaluation on Streaming Graphs |
2020 |
SIGMOD |
8.056119e-05 |
| 1,812 |
Expressive Languages for Path Queries over Graph-Structured Data |
2010 |
PODS |
0.00010467069 |
| 10,912 |
Distinct Shortest Walk Enumeration for RPQs |
2024 |
PODS |
4.1945683e-05 |
| 1,444 |
Finding Regular Simple Paths in Graph Databases |
1989 |
VLDB |
0.00011946075 |
| 4,946 |
Querying Graph Patterns |
2011 |
PODS |
5.8149362e-05 |
| 5,424 |
A Trichotomy for Regular Simple Path Queries on Graphs |
2013 |
PODS |
5.5126983e-05 |
| 11,014 |
Efficient Regular Simple Path Queries under Transitive Restricted Expressions |
2024 |
VLDB |
4.1945683e-05 |