New Compressed Indices for Multijoins on Graph Databases
<|reference_start|>New Compressed Indices for Multijoins on Graph Databases: 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.<|reference_end|>
@article{arroyuelo2024new,
    title={New Compressed Indices for Multijoins on Graph Databases},
    author={Diego Arroyuelo, Fabrizio Barisione, Antonio Fari~na, Adri'an
  G'omez-Brand'on and Gonzalo Navarro},
    journal={arXiv preprint arXiv:2408.00558},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.00558},
    primaryClass={cs.DB cs.DS}
}