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.2856385e-05
- Overall Rank
- 9,743 | 32.29%
- 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 |
| 564 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00020002796 |
| 657 |
An Analytical Study of Large SPARQL Query Logs |
2018 |
VLDB |
0.00018581389 |
| 787 |
Cypher: An Evolving Query Language for Property Graphs |
2018 |
SIGMOD |
0.00016624372 |
| 1,040 |
Querying Graph Databases |
2013 |
PODS |
0.00014483577 |
| 1,255 |
Aggregation and Ordering in Factorised Databases |
2013 |
VLDB |
0.00013011216 |
| 1,452 |
What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? |
2017 |
PODS |
0.00011922523 |
| 1,812 |
Expressive Languages for Path Queries over Graph-Structured Data |
2010 |
PODS |
0.00010458164 |
| 2,216 |
Skew in Parallel Query Processing |
2014 |
PODS |
9.2693784e-05 |
| 2,504 |
Graph Pattern Matching in GQL and SQL/PGQ |
2022 |
SIGMOD |
8.629969e-05 |
| 3,009 |
On Functional Aggregate Queries with Additive Inequalities |
2019 |
PODS |
7.7230513e-05 |
| 3,386 |
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration |
2020 |
PODS |
7.151562e-05 |
| 3,702 |
Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries |
2020 |
VLDB |
6.8251643e-05 |
| 3,831 |
Output-optimal Parallel Algorithms for Similarity Joins |
2017 |
PODS |
6.7146681e-05 |
| 4,709 |
Instance and Output Optimal Parallel Algorithms for Acyclic Joins |
2019 |
PODS |
5.9744219e-05 |
| 5,527 |
Representing Paths in Graph Database Pattern Matching |
2023 |
VLDB |
5.4573655e-05 |
| 5,859 |
Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries |
2021 |
PODS |
5.2963939e-05 |
| 5,905 |
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication |
2015 |
PODS |
5.2746158e-05 |
| 5,963 |
Beyond Equi-joins: Ranking, Enumeration and Factorization |
2021 |
VLDB |
5.2485815e-05 |
| 6,647 |
Fast Join Project Query Evaluation using Matrix Multiplication |
2020 |
SIGMOD |
4.9729424e-05 |
| 7,060 |
Fast Matrix Multiplication for Query Processing |
2024 |
PODS |
4.8401037e-05 |
| 7,762 |
Space-Time Tradeoffs for Conjunctive Queries with Access Patterns |
2023 |
PODS |
4.6542406e-05 |
| 8,587 |
Output-Optimal Algorithms for Join-Aggregate Queries |
2025 |
PODS |
4.4853975e-05 |
| 8,803 |
Conjunctive Regular Path Queries under Injective Semantics |
2023 |
PODS |
4.4426077e-05 |
| 8,972 |
Output-sensitive Conjunctive Query Evaluation |
2024 |
PODS |
4.4150824e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 11,387 |
Answering Regular Path Queries through Exemplars |
2022 |
VLDB |
4.1905499e-05 |
| 1,040 |
Querying Graph Databases |
2013 |
PODS |
0.00014483577 |
| 3,659 |
The Complexity of Evaluating Path Expressions in SPARQL |
2012 |
PODS |
6.8684407e-05 |
| 2,832 |
Regular Path Query Evaluation on Streaming Graphs |
2020 |
SIGMOD |
8.048358e-05 |
| 1,812 |
Expressive Languages for Path Queries over Graph-Structured Data |
2010 |
PODS |
0.00010458164 |
| 10,916 |
Distinct Shortest Walk Enumeration for RPQs |
2024 |
PODS |
4.1905499e-05 |
| 1,445 |
Finding Regular Simple Paths in Graph Databases |
1989 |
VLDB |
0.00011937596 |
| 4,949 |
Querying Graph Patterns |
2011 |
PODS |
5.8090034e-05 |
| 5,435 |
A Trichotomy for Regular Simple Path Queries on Graphs |
2013 |
PODS |
5.5074113e-05 |
| 11,017 |
Efficient Regular Simple Path Queries under Transitive Restricted Expressions |
2024 |
VLDB |
4.1905499e-05 |