Skip to main content

DESARROLLO DE ALMACENAMIENTO COMPACTO PARA PLATAFORMAS DE DATOS GEOESPACIALES LISTOS PARA EL ANALISIS

PID2024-155657OB-C22

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal para la Investigación y el Desarrollo Experimental
Subprogram Subprograma Estatal de Generación de Conocimiento Científico-Técnico y Desarrollo Experimental
Call Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Call year 2024
State Plan 2024-2027 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDADE DA CORUÑA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

Multilevel Representations of Multiple Geographical Objects

  • Gutiérrez-Asorey, Pablo
  • Brisaboa, Nieves R.
  • Cortiñas, Alejandro
  • Rodríguez Luaces, Miguel
  • Paramá, José R.
  • Varela Rodeiro, Tirso
[Abstract]: In this work, we explore different solutions for the problem of representing and querying geographical objects at different scales (zoom levels). In Geographic Information Systems (GIS), the maps we see when looking at the world at a planetary scale versus seeing the detailed coast of one province of a particular country are typically different, since GIS stores several maps, each with the appropriate level of detail for visualizing at a different scale. With the technique presented in this paper, it is possible to store and query the data of multiple geographical objects at different levels of scale, drastically reducing space consumption., This work was supported by the 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); and by Spain’s INE (National Statistics Institute); MICIU/AEI/10.13039/501100011033 EU/ERDF A way of making Europe: [OASSIS-UDC: ED431G 2023/01], [EarthDL: PID2022-141027NB-C21]); [AGRARD: PID2024-155657OB-C22]; by UE FEDER [0079_ATEMPO_6_E], [0064 _GRESINT_1_E]., Xunta de Galicia; ED431G 2023/01
RUC. Repositorio da Universidade da Coruña
Publication Artículo científico (JournalArticle)

K Nearest Neighbor Join Algorithms for Spatial Data Using Compact and Plain Data Structures in Main Memory

  • Bernardo, Guillermo de
  • Rodríguez Penabad, Miguel
  • Corral, Antonio
  • Vassilakopoulos, Michael
  • Brisaboa, Nieves R.
Financiado para publicación en acceso aberto: CRUE-CSIC/Springer Nature Data sets used in the experimental evaluation of this work are available at https://doi.org/10.5281/zenodo.17544411, [Abstract] The K Nearest Neighbors Query (KNNQ) is a fundamental distance-based query with applications in Geographic Information Systems (GIS) and many other domains. The K Nearest Neighbors Join Query (KNNJQ) combines KNNQ with the join operation to find the K nearest neighbors from a dataset P to every object in another dataset Q. Due to the large number of distance computations involved, KNNJQ is an expensive operation that poses a challenge for in-memory systems. In this paper, we propose and evaluate novel in-memory algorithms for KNNQ and KNNJQ using the compact data structure k2-tree. The proposed algorithms exploit hierarchical spatial decomposition together with grouping, pre-processing and progressive pruning techniques. In addition, we develop two new plane-sweep algorithms for KNNQ and KNNJQ, that improve the brute-force algorithms by reducing redundant computations. We conduct an extensive experimental evaluation using real-world spatial datasets to evaluate the performance of our KNNQ and KNNJQ algorithms, comparing them with KD-tree and R*-tree based algorithms. Our results highlight the efficiency of pruning techniques in k2-trees, which reduce distance computations and response time by up to an order of magnitude in KNNJQ, in comparison with the equivalent KD-tree, R*-tree and plane-sweep algorithms., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Guillermo de Bernardo, Miguel R. Penabad and Nieves R. Brisaboa are partially funded by GAIN/Xunta de Galicia [ED431C 2025/34]; by MCIN/AEI/10.13039/501100011033 and EU/ERDF A way of making Europe [PID2021-122554OB-C33 (OASSIS)]; by MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR [PID2024-155657OB-C22 (AGRARD)]; by GAIN and MRR funds. PRTR, (C17.I1). Complementary Plans Biotechnology applied to Health; by European Union through the Interreg Spain-Portugal / POCTEP [0079_ATEMPO_6_E, 0064_GRESINT_1_E]; and by Spain’s INE (National Statistics Intitute). 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 work by Antonio Corral and Michael Vassilakopoulos was funded by MCIN/AEI/10.13039/501100011033 and “ERDF A way of making Europe” grant PID2021-124124OB-I00., Xunta de Galicia; ED431C 2025/34, Xunta de Galicia; ED431G 2023/01, Interreg España-Portugal; 0079_ATEMPO_6_E, Interreg España-Portugal; 0064_GRESINT_1_E, https://doi.org/10.5281/zenodo.17544411