cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918353503780864 |
|---|---|
| author | Park, Sungwoo Kim, Seohyeon Kim, Min-Soo |
| author_facet | Park, Sungwoo Kim, Seohyeon Kim, Min-Soo |
| contents | Regular path queries (RPQs) are fundamental for path-constrained reachability analysis, and more complex variants such as conjunctive regular path queries (CRPQs) are increasingly used in graph analytics. Evaluating these queries is computationally expensive, but to the best of our knowledge, no prior work has explored GPU acceleration. In this paper, we propose cuRPQ, a high-performance GPU-optimized framework for processing RPQs and CRPQs. cuRPQ addresses the key GPU challenges through a novel traversal algorithm, an efficient visited-set management scheme, and a concurrent exploration-materialization strategy. Extensive experiments show that cuRPQ outperforms state-of-the-art methods by orders of magnitude, without out-of-memory errors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20748 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries Park, Sungwoo Kim, Seohyeon Kim, Min-Soo Databases Regular path queries (RPQs) are fundamental for path-constrained reachability analysis, and more complex variants such as conjunctive regular path queries (CRPQs) are increasingly used in graph analytics. Evaluating these queries is computationally expensive, but to the best of our knowledge, no prior work has explored GPU acceleration. In this paper, we propose cuRPQ, a high-performance GPU-optimized framework for processing RPQs and CRPQs. cuRPQ addresses the key GPU challenges through a novel traversal algorithm, an efficient visited-set management scheme, and a concurrent exploration-materialization strategy. Extensive experiments show that cuRPQ outperforms state-of-the-art methods by orders of magnitude, without out-of-memory errors. |
| title | cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries |
| topic | Databases |
| url | https://arxiv.org/abs/2602.20748 |