Indexicon: A Spatial Indexing Library
2026-06-03 • Databases
DatabasesComputational Geometry
AI summaryⓘ
The authors noticed that existing tools for organizing spatial data in open-source projects are limited, complicated, or inconsistent. To fix this, they created Indexicon, a simple and flexible C++ library that includes many popular spatial data structures like R-trees and KD-trees. Each structure is easy to use and supports common operations like searching and updating data. They tested Indexicon on real geographic data and found it performs as well or better than other well-known libraries. The authors also shared their library and data openly to help others do spatial research more easily.
Spatial indexingGeographic Information Systems (GIS)R-treeQuad-treeKD-treeSpatial access methodsRange queriesk-nearest neighbor (kNN)Open-source libraryPerformance evaluation
Authors
Panagiotis Simatis, Panagiotis Bouros, Nikos Mamoulis
Abstract
Spatial indexing is foundational to Geographic Information Systems (GIS) and multi-dimensional data management, yet the current open-source landscape poses a significant barrier to research that employs or benchmarks spatial access methods. We observe that most of the existing open-source libraries include a single index. Some are hindered by complex dependencies, missing critical functionalities, inconsistent APIs, and rigid constraints regarding the support of spatial data types. To address this issue, we introduce Indexicon: a unified, highly portable, extendable, open-source spatial indexing library, designed specifically for rapid integration and ease of modification of main-memory spatial access methods. Indexicon provides a comprehensive suite of popular tree-based spatial access methods, including the R-tree, Quad-tree variants, and the KD-tree. Each structure is meticulously implemented as a self-contained, single-file, header-only C++ template with zero external dependencies beyond the standard library. Crucially, every index features a uniform interface, natively supporting bulk-loading, dynamic insertions/deletions, range queries, $k$-nearest neighbor ($k$NN) search, and structural statistics tracking. We also present an extensive performance evaluation of Indexicon against well-established and widely used implementations of these structures (including Boost Geometry, PCL, and Nanoflann) across six real-world geographic datasets. Our results demonstrate that Indexicon's lightweight design matches or outperforms existing state-of-the-art implementations while offering unmatched architectural flexibility. To foster reproducible spatial research, we open-source the complete library alongside our datasets and query workloads.