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
2008
Venue
PODS
Year
2025
Pagerank
5.3016261e-05
Overall Rank
9,235 | 36.64%
DOI
10.1145/3725242

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
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
530 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.0001709169
547 Cypher: An Evolving Query Language for Property Graphs 2018 SIGMOD 0.00016731552
747 Querying Graph Databases 2013 PODS 0.00014400452
860 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013560445
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
1,448 Skew in Parallel Query Processing 2014 PODS 0.00010758872
1,575 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010318258
1,836 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 9.6489549e-05
2,266 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.8391372e-05
2,462 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 8.5487602e-05
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
2,777 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.1352657e-05
4,371 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.738679e-05
4,781 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.5116536e-05
5,364 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.2472125e-05
5,418 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.2255373e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,996 The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 2015 PODS 6.0150613e-05
6,444 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.8774519e-05
6,678 Output-sensitive Conjunctive Query Evaluation 2024 PODS 5.8053953e-05
6,885 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7464502e-05
7,195 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.6765621e-05
8,190 Conjunctive Regular Path Queries under Injective Semantics 2023 PODS 5.4700577e-05
Previous Page 1 / 1 Next

Semantically Similar Papers