TY - JOUR

T1 - Efficient computation of spatial queries over points stored in k2-tree compact data structures

AU - Santolaya, Fernando

AU - Caniupán, Mónica

AU - Gajardo, Luis

AU - Romero, Miguel

AU - Torres-Avilés, Rodrigo

N1 - Funding Information:
Mónica Caniupán is partially funded by projects DIUBB [ 181315 3/R ] and [ 2030228 IF/R ]. Rodrigo Torres-Avilés were funded by project DIUBB [ 181315 3/R ]. Miguel Romero was funded by project DIUBB [ 163319 3/I ] and [ 2030228 IF/R ]. The authors are part of the Algorithms and Databases Research Group [195119 GI/VC].
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2021/11/12

Y1 - 2021/11/12

N2 - We present efficient algorithms to compute two spatial queries over points stored in compact data structures. The former is the K-Nearest Neighbors Query (KNN) which given a point q gets the K-nearest points to q. The latter query is the K-Closest Pair Query (KCPQ), which obtains the K-pairs of closest neighbors between two set of points R and S on the same spatial plane. There are several efficient implementations of these queries, which work mainly with data stored in secondary memory. However, these implementations do not scale well over large datasets. Our algorithms compute the queries over large datasets of points stored in compact data structures, in main memory. Compact data structures are structures that allow efficiently storage data in main memory and query them in their compressed form. We use the k2-tree compact structure to represent points of interest. Through experimentation over synthetic and real datasets, we show that by using the k2-tree we can work with large datasets in main memory, and that the KNN and KCPQ spatial data queries can be efficiently computed over the compact data structures. We also implement a JAVA library that is available for the academic and industrial community.

AB - We present efficient algorithms to compute two spatial queries over points stored in compact data structures. The former is the K-Nearest Neighbors Query (KNN) which given a point q gets the K-nearest points to q. The latter query is the K-Closest Pair Query (KCPQ), which obtains the K-pairs of closest neighbors between two set of points R and S on the same spatial plane. There are several efficient implementations of these queries, which work mainly with data stored in secondary memory. However, these implementations do not scale well over large datasets. Our algorithms compute the queries over large datasets of points stored in compact data structures, in main memory. Compact data structures are structures that allow efficiently storage data in main memory and query them in their compressed form. We use the k2-tree compact structure to represent points of interest. Through experimentation over synthetic and real datasets, we show that by using the k2-tree we can work with large datasets in main memory, and that the KNN and KCPQ spatial data queries can be efficiently computed over the compact data structures. We also implement a JAVA library that is available for the academic and industrial community.

KW - Algorithms

KW - Compact data structures

KW - Computational geometry

KW - Spatial databases

KW - Spatial queries

UR - http://www.scopus.com/inward/record.url?scp=85114984306&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.09.012

DO - 10.1016/j.tcs.2021.09.012

M3 - Article

AN - SCOPUS:85114984306

SN - 0304-3975

VL - 892

SP - 108

EP - 131

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -