RUC. Repositorio da Universidade da Coruña
Publicación
Artículo científico (JournalArticle)
Classic distance join queries using compact data structures
[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
Proyecto:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2021-122554OB-C33
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2020-114635RB-I00
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2019-105221RB-C41
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2021-124124OB-I00
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 TED2021-129245B-C21
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PDC2021-121239-C31
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PDC2021-120917-C21
HANDLE: http://hdl.handle.net/2183/36651
Ver en: http://hdl.handle.net/2183/36651