RUC. Repositorio da Universidade da Coruña
Publication
Contribución de congreso (ConferenceOutput)
Cache-Friendly Compressed Boolean Matrices
Traballo 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%., This work is supported by ANID – Millennium Science Initiative Program – Code ICN17_002, and Fondecyt Grant 1-230755; CITIC is funded by the Xunta de Galicia and co-financed by the EU through FEDER Galicia [ED431G 2023/01]; MCIN/AEI and EU/ERDF A way of making Europe Grants [PID2022-141027NB-C21 (EarthDL), PID2021-122554OB-C33 (Oassis)]; MCIN/AEI and NextGenerationEU/PRTR Grants [PID2020-114635RB-I00 (EXTRACOMPACT), TED2021-129245B-C21 (PLAGEMIS)]., Xunta de Galicia; ED431G 2023/01, Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-230755
Project:
AEI / Plan Estatal de Investigación Científica PID2022-141027NB-C21
,
AEI / Técnica y de Innovación 2021-2023 PID2021-122554OB-C33
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2020-114635RB-I00
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 TED2021-129245B-C21
View at: https://hdl.handle.net/2183/46376