Cache-Friendly Compressed Boolean Matrices
| UDC.coleccion | Investigación | |
| UDC.conferenceTitle | SPIRE 2025 | |
| UDC.departamento | Ciencias da Computación e Tecnoloxías da Información | |
| UDC.grupoInv | Laboratorio de Bases de Datos (LBD) | |
| UDC.institutoCentro | CITIC - Centro de Investigación de Tecnoloxías da Información e da Comunicación | |
| dc.contributor.author | Fariña, Antonio | |
| dc.contributor.author | Gómez-Brandón, Adrián | |
| dc.contributor.author | Gómez-Colomer, Asunción | |
| dc.contributor.author | Navarro, Gonzalo | |
| dc.date.accessioned | 2025-11-10T13:52:25Z | |
| dc.date.available | 2025-11-10T13:52:25Z | |
| dc.date.issued | 2025-09-22 | |
| dc.description | 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) | |
| dc.description.abstract | [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%. | |
| dc.description.sponsorship | 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)]. | |
| dc.description.sponsorship | Xunta de Galicia; ED431G 2023/01 | |
| dc.description.sponsorship | Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-230755 | |
| dc.identifier.citation | Fariñ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_9 | |
| dc.identifier.doi | 10.1007/978-3-032-05228-5_9 | |
| dc.identifier.isbn | 978-3-032-05228-5 | |
| dc.identifier.uri | https://hdl.handle.net/2183/46376 | |
| dc.language.iso | eng | |
| dc.publisher | Springer | |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica, Técnica y de Innovación 2021-2023/PID2022-141027NB-C21/ES/MODELADO, DESCUBRIMIENTO, EXPLORACION Y ANALISIS DE DATA LAKES MEDIOAMBIENTALES | |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PID2021-122554OB-C33/ES/OASSIS-UDC: HACIA ORGANIZACIONES SOFTWARE MÁS SOSTENIBLES: UN ENFOQUE HOLÍSTICO PARA PROMOVER LA SOSTENIBILIDAD ECONÓMICA, HUMANA Y MEDIOAMBIENTAL | |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-114635RB-I00/ES/EXPLOTACION ENRIQUECIDA DE TRAYECTORIAS CON ESTRUCTURAS DE DATOS COMPACTAS Y GIS/ | |
| dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/TED2021-129245B-C21/ES/PLATAFORMA PARA LA GENERACIÓN AUTOMÁTICA DE SISTEMAS DE INFORMACIÓN DE LA MOVILIDAD ENERGÉTICAMENTE EFICIENTES, BASADOS EN ESTRUCTURAS DE DATOS COMPACTAS Y GIS (PLAGEMIS) | |
| dc.relation.uri | https://doi.org/10.1007/978-3-032-05228-5_9 | |
| dc.rights | © 2026 The Author(s), under exclusive license to Springer Nature Switzerland AG | |
| dc.rights.accessRights | embargoed access | |
| dc.subject | Compact Data Structures | |
| dc.subject | Algebra | |
| dc.subject | Binary Matrices | |
| dc.subject | Cache-Friendly | |
| dc.title | Cache-Friendly Compressed Boolean Matrices | |
| dc.type | conference output | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 2fe2b113-791f-4229-a83a-311d0c8b5ce6 | |
| relation.isAuthorOfPublication | 1a99c615-806a-48b0-8e5f-7772467f275d | |
| relation.isAuthorOfPublication.latestForDiscovery | 2fe2b113-791f-4229-a83a-311d0c8b5ce6 |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Farina_Antonio_2026_Cache_Friendly_Compressed_Boolean_Matrices.pdf
- Size:
- 407.64 KB
- Format:
- Adobe Portable Document Format