New Compressed Indices for Multijoins on Graph Databases
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916342703063040 |
|---|---|
| author | Arroyuelo, Diego Barisione, Fabrizio Fariña, Antonio Gómez-Brandón, Adrián Navarro, Gonzalo |
| author_facet | Arroyuelo, Diego Barisione, Fabrizio Fariña, Antonio Gómez-Brandón, Adrián Navarro, Gonzalo |
| contents | A recent surprising result in the implementation of worst-case-optimal (wco) multijoins in graph databases (specifically, basic graph patterns) is that they can be supported on graph representations that take even less space than a plain representation, and orders of magnitude less space than classical indices, while offering comparable performance. In this paper we uncover a wide set of new wco space-time tradeoffs: we (1) introduce new compact indices that handle multijoins in wco time, and (2) combine them with new query resolution strategies that offer better times in practice. As a result, we improve the average query times of current compact representations by a factor of up to 13 to produce the first 1000 results, and using twice their space, reduce their total average query time by a factor of 2. Our experiments suggest that there is more room for improvement in terms of generating better query plans for multijoins. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00558 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Compressed Indices for Multijoins on Graph Databases Arroyuelo, Diego Barisione, Fabrizio Fariña, Antonio Gómez-Brandón, Adrián Navarro, Gonzalo Databases Data Structures and Algorithms A recent surprising result in the implementation of worst-case-optimal (wco) multijoins in graph databases (specifically, basic graph patterns) is that they can be supported on graph representations that take even less space than a plain representation, and orders of magnitude less space than classical indices, while offering comparable performance. In this paper we uncover a wide set of new wco space-time tradeoffs: we (1) introduce new compact indices that handle multijoins in wco time, and (2) combine them with new query resolution strategies that offer better times in practice. As a result, we improve the average query times of current compact representations by a factor of up to 13 to produce the first 1000 results, and using twice their space, reduce their total average query time by a factor of 2. Our experiments suggest that there is more room for improvement in terms of generating better query plans for multijoins. |
| title | New Compressed Indices for Multijoins on Graph Databases |
| topic | Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.00558 |