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

• Published in: Theoretical computer science 2021-11, Vol.892, p.108-131
• Main Authors: Santolaya, Fernando, Caniupán, Mónica, Gajardo, Luis, Romero, Miguel, Torres-Avilés, Rodrigo
• Format: Article
• Language: English
• Subjects: Algorithms; Compact data structures; Computational geometry; Spatial databases; Spatial queries
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2021.09.012

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.