Fariña, AntonioGómez-Brandón, AdriánGómez-Colomer, AsunciónNavarro, Gonzalo2025-11-102025-11-102025-09-22Fariña, A., Gómez-Brandón, A., Gómez-Colomer, A., Navarro, G. (2026). Cache-Friendly Compressed Boolean Matrices. In: Badkobeh, G., Radoszewski, J., Tonellotto, N., Baeza-Yates, R. (eds) String Processing and Information Retrieval. SPIRE 2025. Lecture Notes in Computer Science, vol 16073. Springer, Cham. https://doi.org/10.1007/978-3-032-05228-5_9978-3-032-05228-5https://hdl.handle.net/2183/46376Traballo presentado en: String Processing and Information Retrieval, 32nd International Symposium, SPIRE 2025, London, UK, September 8–11, 2025. This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-032-05228-5_9 Part of the book series: Lecture Notes in Computer Science (LNCS; volume 16073)[Abstract]: We introduce a new compressed representation of sparse Boolean matrices that enjoys reference locality properties. We build on an existing representation based on LOUDS-deployed cardinal trees, and design one based instead on DFUDS. While this brings various complications, we show that the resulting matrix representation is considerably faster to carry out sums and multiplications, with speedups of up to 60%.eng© 2026 The Author(s), under exclusive license to Springer Nature Switzerland AGCompact Data StructuresAlgebraBinary MatricesCache-Friendlyconference outputembargoed access10.1007/978-3-032-05228-5_9