Pasar al contenido principal

UN MARCO FORMAL BASADO EN LA WEB DE LAS COSAS Y COMPUTACION EDGE PARA LA DEFINICION, EL DESCUBRIMIENTO Y EL PROCESAMIENTO DE DATOS DE COMPONENTES CIBERFISICOS

PID2021-124124OB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2021
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE ALMERIA

Resultados relacionados

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

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

Classic distance join queries using compact data structures

  • Bernardo, Guillermo de
  • Penabad, Miguel R.
  • Corral, Antonio
  • Brisaboa, Nieves R.
[Abstract]: Distance-based Join Queries (DJQs) have multiple applications in spatial databases, Geographic Information Systems, and other areas. The K Closest Pairs Query (KCPQ) and the 𝜀� Distance Join Query (𝜀� DJQ) are well-known DJQs that have been widely studied and can be solved using plane-sweep techniques, which are efficient but must keep the whole datasets in main memory. In this work, we propose DJQ algorithms that work with data represented using a k2-tree, a compact data structure for binary grids. Our algorithms solve KCPQ and 𝜀� DJQ queries, as well as several window-constrained variants, taking advantage of the indexing capabilities of K2 -trees to efficiently answer queries without the need to decompress the data. Our experimental evaluation with large datasets shows that k2-tree algorithms are up to 5 times faster than plane-sweep algorithms in KCPQ, and 5–30 times faster in 𝜀� DJQ. In variants that are window-constrained, our algorithms are competitive in most scenarios and faster for large windows. Additionally, our algorithms are not very affected by the distribution of the data and yield much more predictable query times, showing up to 30 times smaller variance in query times than plane sweep, depending on the location of the query window., Guillermo de Bernardo, Miguel R. Penabad and Nieves R. Brisaboa are partially funded by MCIN/AEI/10.13039/501100011033 and EU/ERDF A way of making Europe [PID2021-122554OB-C33 (OASSIS)]; by MCIN/AEI/10.13039/501100011033 [PID2020-114635RB-I00 (EXTRACompact), PID2019-105221RB-C41 (MAGIST)]; by MCIN/AEI/10.13039/501100011033 and “NextGenerationEU”/PRTR [TED2021-129245B-C21 (PLAGEMIS), PDC2021-121239-C31 (FLATCITY-POC), PDC2021-120917-C21 (SIGTRANS)]; and by GAIN/Xunta de Galicia [ED431C 2021/53]. CITIC is funded by the Xunta de Galicia through the collaboration agreement between the Department of Culture, Education, Vocational Training and Universities and the Galician universities for the reinforcement of the research centers of the Galician University System (CIGUS) [ED431G 2019/01 (CSI)]. The work by Antonio Corral was partially funded by the EU ERDF and the Andalusian Government (Spain) under the project UrbanITA (ref. PY20_00809) and grant PID2021-124124OB-I00 funded by the Spanish Government MCIN/AEI/10.13039/501100011033 and the “ERDF A way of making Europe”. Funding for open access charge: Universidade da Coruña/CISUG., Xunta de Galicia; ED431C 2021/53, Xunta de Galicia; ED431G 2019/01, Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG
RUC. Repositorio da Universidade da Coruña
Publicación 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