DBScholar

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
h873222240f66c9b6
Venue
PODS
Year
2025
Pagerank
5.1630894e-05
Overall Rank
9,445 | 36.69%
DOI
10.1145/3725242
PDF
Download (CC BY 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{khamis_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Output-Sensitive Evaluation of Regular Path Queries}},
        url = {https://dl.acm.org/doi/10.1145/3725242},
        doi = {10.1145/3725242},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Khamis, Mahmoud Abo and Kara, Ahmet and Olteanu, Dan and Suciu, Dan},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 cited papers.

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

Rank Cited Paper Year Venue Pagerank
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
420 Cypher: An Evolving Query Language for Property Graphs 2018 SIGMOD 0.00018489392
536 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016738841
719 Querying Graph Databases 2013 PODS 0.00014493767
848 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013463236
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
1,428 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 0.000106884
1,474 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010526746
1,483 Skew in Parallel Query Processing 2014 PODS 0.00010500209
2,316 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6404062e-05
2,475 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 8.3947133e-05
2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2157154e-05
2,766 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0221503e-05
4,487 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5628751e-05
4,714 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4395938e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
5,514 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.0866191e-05
5,574 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.0628579e-05
6,136 The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 2015 PODS 5.8578818e-05
6,482 Output-sensitive Conjunctive Query Evaluation 2024 PODS 5.7529053e-05
6,579 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7252637e-05
6,585 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7238683e-05
7,361 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.528228e-05
8,380 Conjunctive Regular Path Queries under Injective Semantics 2023 PODS 5.3271197e-05
Previous Page 1 / 1 Next

Semantically Similar Papers