Arroyuelo, DiegoBarisione, FabrizioFariña, AntonioGómez-Brandón, AdriánNavarro Badino, Gonzalo2025-11-262025-11-262025-11-13ARROYUELO, D., BARISIONE, F., FARIÑA, A., GÓMEZ-BRANDÓN, A. y NAVARRO, G., 2026. New compressed indices for multijoins on graph databases. Information Systems [en línea], vol. 137, pp. 102647. [consulta: 26 noviembre 2025]. ISSN 03064379. DOI 10.1016/j.is.2025.102647. Disponible en: https://linkinghub.elsevier.com/retrieve/pii/S0306437925001334.https://hdl.handle.net/2183/46548Funding for open access charge: Universidade da Coruña/CISUG .[Abstract] 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.engAttribution-NonCommercial-NoDerivatives 4.0 Internationalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Worst-case-optimalMultijoinsGraph databasesCompact data structuresjournal articleopen access10.1016/j.is.2025.102647