k2-MS: A Compact Data Structure for Raster Datasets
| UDC.coleccion | Investigación | |
| 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 | |
| UDC.journalTitle | Geoinformatica | |
| UDC.startPage | 24 | |
| UDC.volume | 30 | |
| dc.contributor.author | Saavedra, Miguel | |
| dc.contributor.author | Gutiérrez, Gilberto | |
| dc.contributor.author | Bernardo, Guillermo de | |
| dc.date.accessioned | 2026-07-28T09:46:11Z | |
| dc.date.available | 2026-07-28T09:46:11Z | |
| dc.date.issued | 2026 | |
| dc.description | 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/s10707-026-00578-y The data that support the findings of this study are available in WorldClim at https://www.worldclim.org/data/worldclim21.html. These data were derived from the following resource available in the public domain: WorldClim - Global Climate Data (Version 2.1). | |
| dc.description.abstract | [Abstract]: In this work, we present the compact data structure k2-MS for the representation of raster coverages. k2-MS is based on a sequence of binary matrices (each represented by a k2-tree), which correspond to the binary encoding of the thematic variable values of the raster. The properties of the k2-MS data structure allow it to benefit from the processor instructions PDEP and PEXT, significantly reducing the access time to the structure. Through a series of experiments on different datasets, we evaluated the performance of our structure by comparing it with the k2-raster, one of the most competitive structures reported in the literature. On average, when comparing the best configurations of both approaches, k2-MS is 48% faster for Window queries and 43% faster for Window Range queries, while requiring about 63% of the storage space used by the k2-raster. | |
| dc.description.sponsorship | This work was funded by the FONDECYT Regular project 1230647. Guillermo de Bernardo was partially funded by GAIN/Xunta de Galicia (ref. ED431C 2025/34), GAIN and MRR funds. PRTR, (C17.I1), European Union through the Interreg Spain-Portugal / POCTEP (refs. 0079_ATEMPO_6_E and 0064_GRESINT_1_E), MCIN/AEI/10.13039/501100011033 and EU/ERDF A way of making Europe (ref. PID2021-122554OB-C33) and MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR (ref. TED2021-129245B-C21). CITIC, as a center accredited for excellence within the Galician University System and a member of the CIGUS Network, receives subsidies from the Department of Education, Science, Universities, and Vocational Training of the Xunta de Galicia. Additionally, it is co-financed by the EU through the FEDER Galicia 2021-27 operational program (ref. ED431G 2023/01). The APC was funded by FONDECYT Regular project 1230647. | |
| dc.description.sponsorship | Chile. Fondo Nacional de Desarrollo Científico y Tecnológico; 1230647 | |
| dc.description.sponsorship | Xunta de Galicia; ED431C 2025/34 | |
| dc.description.sponsorship | Xunta de Galicia; ED431G 2023/01 | |
| dc.description.sponsorship | Interreg España-Portugal; 0079_ATEMPO_6_E | |
| dc.description.sponsorship | Interreg España-Portugal; 0064_GRESINT_1_E | |
| dc.identifier.citation | Saavedra, M., Gutiérrez, G. & de Bernardo, G. k2-MS: A Compact Data Structure for Raster Datasets. Geoinformatica 30, 24 (2026). https://doi.org/10.1007/s10707-026-00578-y | |
| dc.identifier.doi | 10.1007/s10707-026-00578-y | |
| dc.identifier.issn | 1573-7624 | |
| dc.identifier.uri | https://hdl.handle.net/2183/48949 | |
| dc.language.iso | eng | |
| dc.publisher | Springer Nature | |
| dc.relation.isbasedon | https://www.worldclim.org/data/worldclim21.html | |
| 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 MAS SOSTENIBLES: UN ENFOQUE HOLISTICO PARA PROMOVER LA SOSTENIBILIDAD ECONOMICA, 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 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/s10707-026-00578-y | |
| dc.rights | © 2026, The Author(s), under exclusive licence to Springer Science Business Media, LLC, part of Springer Nature | |
| dc.rights.accessRights | embargoed access | |
| dc.subject | Compact Data Structures | |
| dc.subject | Raster Data | |
| dc.subject | Geographic Information Systems | |
| dc.subject | Spatial Data Structures | |
| dc.subject | Spatial Algorithms | |
| dc.title | k2-MS: A Compact Data Structure for Raster Datasets | |
| dc.type | journal article | |
| dc.type.hasVersion | AM | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 23354397-ec74-4cbb-93ac-f85352e9fbd8 | |
| relation.isAuthorOfPublication.latestForDiscovery | 23354397-ec74-4cbb-93ac-f85352e9fbd8 |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Bernardo_Guillermode_2026_k2_MS.pdf
- Size:
- 1003.85 KB
- Format:
- Adobe Portable Document Format