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.1826718e-05
Overall Rank
9,410 | 36.74%
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
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
419 Cypher: An Evolving Query Language for Property Graphs 2018 SIGMOD 0.0001854669
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016726545
719 Querying Graph Databases 2013 PODS 0.00014529156
849 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013504405
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
1,468 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010566509
1,481 Skew in Parallel Query Processing 2014 PODS 0.00010539119
1,494 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 0.00010502195
2,299 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6727773e-05
2,464 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 8.4260608e-05
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
2,757 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 8.0525756e-05
4,463 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5877664e-05
4,698 Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries 2021 PODS 6.4640177e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
5,487 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.1096421e-05
5,557 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.085853e-05
6,121 The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 2015 PODS 5.8800995e-05
6,467 Output-sensitive Conjunctive Query Evaluation 2024 PODS 5.7747248e-05
6,567 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7469783e-05
6,573 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7455776e-05
7,338 Space-Time Tradeoffs for Conjunctive Queries with Access Patterns 2023 PODS 5.5491953e-05
8,362 Conjunctive Regular Path Queries under Injective Semantics 2023 PODS 5.3473243e-05
Previous Page 1 / 1 Next

Semantically Similar Papers