Use this link to cite:
https://hdl.handle.net/2183/46376 Cache-Friendly Compressed Boolean Matrices
Loading...
Identifiers
Publication date
Authors
Advisors
Other responsabilities
Journal Title
Bibliographic 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
Type of academic work
Academic degree
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%.
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)
Editor version
Rights
© 2026 The Author(s), under exclusive license to Springer Nature Switzerland AG