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

Fernando Santolaya, Mónica Caniupán, Luis Gajardo, Miguel Romero, Rodrigo Torres-Avilés

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish
Pages (from-to)108-131
Number of pages24
JournalTheoretical Computer Science
StatePublished - 12 Nov 2021
Externally publishedYes


  • Algorithms
  • Compact data structures
  • Computational geometry
  • Spatial databases
  • Spatial queries


Dive into the research topics of 'Efficient computation of spatial queries over points stored in k2-tree compact data structures'. Together they form a unique fingerprint.

Cite this