Indexicon: A Spatial Indexing Library

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Indexicon: A Spatial Indexing Library

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

databases datamanagement sql storage

databases, sql, data management, storage

Indexicon: A Spatial Indexing Library Panagiotis Simatis

Panagiotis Bouros

Nikos Mamoulis

Department of CS and Engineering University of Ioannina Ioannina, Greece [email protected]

Institute of Computer Science Johannes Gutenberg University Mainz Mainz, Germany [email protected]

Department of CS and Engineering University of Ioannina Ioannina, Greece [email protected]

arXiv:2606.04676v1 [cs.DB] 3 Jun 2026

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, 𝑘-nearest neighbor (𝑘NN) search, and structural statistics tracking. We also present an extensive performance evaluation of Indexicon against wellestablished and widely used implementations of these structures (including Boost Geometry, PCL, and Nanoflann) across six realworld 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.

Keywords Spatial indexing, access methods, data structures, R-tree, Quad-tree, KD-tree, benchmarking

Two geometry types are typically indexed by such data structures: points and minimum bounding boxes (MBBs). Extended geometries, such as polygons, are approximated by MBBs and the spatial index organizes them and processes the filter step of the spatial query, which retrieves the objects whose MBB satisfies the query predicate. In a refinement step, the exact geometries of these objects are fetched and verified [8]. In the past, several surveys [11, 21, 31, 33, 48, 49] have investigated the performance and the scalability of spatial libraries and multi-dimensional (or spatial) indexing under different settings. However, as (geo)spatial information expands in velocity and applications, ranging from LiDAR point clouds to real-time GPS tracking and from medical to scientific data, the engineering implementation details of spatial structures have become as critical as their achieved query throughput and their theoretical complexity bounds. Essentially, while these benchmarks and surveys offer invaluable insights, they fail to delve into the technical and software engineering challenges of spatial indexing. Researchers and practitioners in the spatial database community face a highly fragmented and rigid open-source software ecosystem. Modern research frequently demands modifying an index to handle non-traditional tasks, specialized hardware acceleration layouts, or non-native query predicates. However, available open-source implementations are typically single-index focused, burdened with deeply nested multi-file dependencies, and incompatible APIs. Furthermore, many libraries omit critical operational capabilities like dynamic deletions, robust bulk-loading routines, or structural statistics reporting. This systemic fragmentation not only prevents true apples-to-apples performance comparisons between data structures in customized search tasks, but also drastically elevates the barrier to entry for developing and testing novel multi-dimensional search algorithms and extensions of spatial data structures. In view of the above, we define the following key challenges in designing and developing libraries for spatial indexing:

Introduction

Spatial computing, geographic information systems (GIS), and modern spatiotemporal architectures rely fundamentally on efficient access methods. Multi-dimensional data structures such as the Quadtree [19, 47, 58], the KD-tree [5] and the R-tree [4, 24], have served as the bedrock of spatial data management for several decades. These indices drastically prune the search space for popular retrieval operations, such as range and nearest neighbor queries and extensions thereof [37]. Besides, proposed solutions for a plethora of data analysis problems, e.g., in computer vision and image retrieval [28, 45, 54, 59, 72], top-𝑘 and ranking search [42–44, 69], skyline computation [16, 32, 40, 50, 51, 61], clustering [2, 12, 17, 18, 27, 53, 71], temporal [14, 60] and uncertain data management [6, 34, 52, 63, 73], among others, rely on and extend spatial indices.

(1) Features and capabilities. An ideal library includes implementations of multiple spatial data structures for indexing different data types (e.g., points and minimum bounding boxes MBB) in both the 2D and 3D space. The library should also support construction and maintenance operations, and offer evaluation methods for different query types. (2) Code complexity and extendability. The spatial index implementations should exhibit low structural and code complexity, allowing researchers and practitioners to rapidly incorporate them into their projects. At the same time, the cost of modifying and adapting the codebase should be low, allowing users to extend the functionality and the feature set of the library, e.g., to design a new index building upon

Simatis et al.

existing ones or to develop and test unsupported (potentially novel) search tasks. (3) Performance. For each included spatial data structure, the library should implement the recommended storage layout and the state-of-the-art index construction and search algorithms in the literature. In addition, it should allow the user to optimize performance by tuning the index parameters (e.g., node capacity), based on the data characteristics and application requirements. As we discuss in Section 2, no existing library or open-source implementation of spatial indexing manages to successfully address all three challenges. To address this, we have developed and we constantly evolve Indexicon1 , a comprehensive spatial indexing library and benchmarking suite tailored for modern main-memory applications. Indexicon is engineered from the ground up to empower researchers and practitioners with a portable, fully opensource, and easily modified development environment. Concretely, our work delivers several contributions: (1) A portable architecture: We consolidate several spatial indexing structures into a single cohesive, header-only C++ framework. By eliminating API discrepancies and requiring zero external dependencies beyond the standard library, Indexicon provides researchers with a highly portable, dropin development environment. (2) A standardized benchmarking suite: To foster reproducible spatial research, we curate a robust evaluation sandbox featuring several real-world geographic datasets that include points or minimum bounding boxes (MBBs) of geometries, while offering custom query generation functionality. (3) A comprehensive empirical evaluation: We present a comprehensive performance study, comparing Indexicon against data structures from widely used spatial libraries, including Boost Geometry, GEOS, PCL, and Nanoflann. By evaluating under identical hardware constraints, data types, and workloads, we eliminate historical benchmarking asymmetries and establish a fair performance baseline. (4) Performance advantage: Our tests reveal that Indexicon successfully matches or even exceeds the ingestion speed and efficiency of popular baselines in core range and 𝑘NN search operations, while providing unprecedented architectural flexibility. Outline. The remainder of this paper is structured as follows. Section 2 overviews the landscape of popular spatial indexing libraries and implementations. Section 3 introduces the design philosophy and internal engineering of the Indexicon library. Section 4 presents our experimental analysis. Finally, Section 5 concludes the paper with directions for future work.

Spatial Indexing Landscape

Table 1 summarizes popular spatial indexing libraries and implementations, in terms of the following features: the supported data 1 The name Indexicon is a lighthearted nod to the classic fictional grimoires, framing

the library as a definitive tome of spatial indexing structures.

types and number of dimensions, construction and maintenance operations, query operations, code complexity and extendibility. Boost Geometry [3]. Geometry is a popular geospatial extension to the Boost library. Out of the common spatial data structures, the library includes only an R-tree implementation, offering however the entire range of features and capabilities. Specifically, the R-tree is an N-dimensional index supporting both point and MBB data. It offers bulk-loading construction and supports insertions, deletions for maintenance. For querying, both range and 𝑘NN search methods are available. On the other hand, the implementation is complex, requiring extensive knowledge of the Boost codebase. Specifically, the R-tree header alone contains over 2K lines and directly includes over 50 headers, many of them for internal components such as, node representation, visitors, updates, etc. Thus, mastering of the general Boost codebase is necessary for possible changes in the structure and functionality of the index. Hence, extending the R-tree structure or writing new search algorithms that use it is not straightforward since the implementation is tightly coupled with library-specific storage, shape, visitor, and query abstractions. Another inflexibility is that the developer cannot set a different capacity between the inner tree nodes and the leaves. CGAL [64]. The CGAL library includes implementations for Orthtrees (CGAL’s terminology for N-dimensional generalizations of Quad-trees and Oct-trees) and KD-trees as N-dimensional indices. Although only points are supported, the key drawback is that the library has limited support for dynamic operations and exact querying. Its Orth-tree is entirely static (supporting bulk-loading but no insertions or deletions), and its range queries return the intersected leaf nodes rather than the matching objects. Likewise, while the KD-tree implementation supports bulk-loading construction, range, and 𝑘NN queries, its insertion mechanism invalidates the structure, requiring a full rebuild before querying, rather than dynamically maintaining the tree. The KD-tree supports lazy deletions as re-balancing is not implemented. Finally, since CGAL is a comprehensive geometry library, it consists of a large interwoven codebase, making it hard to modify without deep knowledge of the library. GEOS [23]. The GEOS library offers implementations for the Rtree and the Quad-tree to index both points and MBBs, but only in the 2D space. In particular, the R-tree implementation supports STR packing. After the tree is built, items may not be added or removed. Regarding querying, it supports range queries, but its nearest-neighbor search is limited to 1-NN queries. The library implements the MX-CIF Quad-tree variant that directly indexes MBBs and boxes, while points are represented as degenerate MBBs where the upper and lower bound at each dimension coincide. It supports dynamic insertion and deletion, but lacks native support for 𝑘NN queries and bulk-loading. Furthermore, its range query only prunes the search to nodes whose extent overlaps the query range, thus, the user must write custom post-filtering code to identify the exact query results. Moreover, both implementations are tightly integrated into the GEOS geometry engine and rely on library-specific elements, thus increasing code complexity and making the indices difficult to extend. Finally, its memory overhead proved too high

Indexicon: A Spatial Indexing Library

Table 1: Overview of popular spatial indexing libraries and implementations Indices

Dimensionality

Data types

Bulk loading

Maintenance

Range queries

𝑘NN queries

Code complexity

Extensibility

Indexicon (this paper) R-tree Quad-tree Oct-tree KD-tree

Any 2D 3D Any

Point/MBB Point/MBB Point Point

✓ ✓ ✓ ✓

Insert/Delete Insert/Delete Insert/Delete Insert/Delete

✓ ✓ ✓ ✓

Low Low Low Low

High High High High

Boost Geometry [3] R-tree

Any

Point/MBB

✓

Insert/Delete

✓

High

Low

CGAL [64] Orth-tree KD-tree

Any Any

Point Point

✓ ✓

Insert (re-build required)/Delete (lazy)

Approximate ✓

✓ ✓

High High

Low Low

GEOS [23] R-tree Quad-tree

2D 2D

Point/MBB Point/MBB

✓ -

Insert/Delete

✓ Approximate

Only for 𝑘 = 1 -

High High

Low Low

LibSpatialIndex [25] R-tree

Any

Point/MBB

✓

Insert/Delete

✓

High

Low

PCL [56] Oct-tree KD-tree

3D 3D

Point Point

✓

Insert -

Float-based Float-based radius

Float-based Float-based

High High

Low Low

Nanoflann [7] KD-tree

Any

Point

✓

Insert/Delete (lazy)

Static only/Dynamic only radius

✓

Medium

High

Vigier [68] Quad-tree

Point/MBB

Insert/Delete

✓

Low

High

for large datasets, resulting in occasional out-of-memory crashes during our evaluation. LibSpatialIndex [25]. The library provides a feature-complete R-tree implementation supporting bulk-loading construction, insertions and deletions for maintenance, range and 𝑘NN queries over N-dimensional objects (points and MBBs). Specifically for dynamic updates, it supports the linear, quadratic, and R*-tree splitting. Although the index can reside in main-memory, the code architecture is disk-oriented which introduces substantial overhead, making it significantly slower than the in-memory alternatives. Moreover, while its codebase is less complex than Boost’s, it is not straightforward to adapt since the R-tree implementation is similar to Boost’s tightly coupled with library-specific storage, shape, visitor, and query abstractions. PCL [56]. The Point Cloud Library (PCL) provides Oct-tree and KD-tree implementations for 3D points. Both store coordinates as float values, making direct comparison against indices that support double-precision coordinates hard. For range queries in the Oct-tree, this limitation is addressed by expanding each query bound by one representable float value and post-filtering the returned candidates against the original double-precision coordinates. However, this single-precision representation may still misrank candidates for 𝑘NN queries, where post-filtering is not sufficient to guarantee the exact double-precision result. PCL’s KD-tree is based on FLANN [44]. It supports bulk-loading construction but does not expose insertion or deletion through the PCL wrapper. In contrast, PCL’s Oct-tree is populated through point insertions rather than a packed bulk-loading procedure, and its deletion API removes the entire leaf addressed by a point, instead of the individual point record. Nanoflann [7]. Nanoflann is a popular KD-tree implementation supporting points in an 𝑁 -dimensional space. It provides distinct index adaptors for static and dynamic data. The static tree supports

bulk-loading construction and exact window range queries. In contrast, the dynamic adaptor (which is implemented as a forest of static KD-trees) supports incremental insertions and deletions, but only exposes a radius-shape range query interface. Furthermore, its construction is handled by grouping points into bins that are individually bulk-loaded into multiple KD-trees, while point deletions are handled lazily using tombstones. A workaround to evaluate window range queries on the dynamic adaptor is to perform an enclosing-ball radius search and then post-filter the returned candidates against the exact query MBB. Vigier [68]. Vigier’s library implements an MX-CIF Quad-tree, supporting both points and MBB data. Crucially, it does not support bulk-loading construction and requires an a priori global bounding box upon initialization, as it cannot dynamically expand to accommodate out-of-bounds insertions. Furthermore, it supports spatial range queries but lacks 𝑘NN search.

The Indexicon Library

We now describe our Indexicon library for spatial indexing which directly tackles the challenges listed in Section 1. Indexicon is opensourced at https://github.com/psimatis/Indexicon-Spatial-Library.

3.1

Code architecture and API

A primary goal of Indexicon is to avoid the fragmented interfaces prevalent in existing libraries. Thus, all indices adhere to a common architectural pattern and a unified C++ interface, regardless of their underlying algorithms. As illustrated in Listing 1, each index is instantiated as a standalone C++ template, parameterized by the coordinate type, payload identifier type, dimensionality, and node capacity. This avoids the heavy, interwoven class hierarchies found in libraries like Boost or CGAL, allowing developers to drop the headers directly into their projects. The interface standardizes all core spatial operations. Indices can be dynamically populated from

Simatis et al.

template <typename Coord, typename Value, unsigned int Dims, unsigned int Cap> class SpatialIndex { public: SpatialIndex(); // Bulk-loading constructor template <typename Iter> SpatialIndex(const Iter first, const Iter last); // Maintenance void insert(const Point p); void insert(const MBB b); bool remove(const Point p); bool remove(const MBB b); // Range search template <typename Result> Result rangeQuery(const MBB q); // kNN Search template <typename Result> Result knnQuery(const Point q, const unsigned int k); // Structural metrics Stats getStatistics(); };

Listing 1: The API template of Indexicon

an empty state or efficiently bulk-loaded using an iterator range. Dynamic maintenance is handled via insert and remove methods. For data retrieval, the API supports both window range queries (rangeQuery) and 𝑘-nearest neighbor searches (knnQuery). Search results are directly emitted to a provided C++ result container. This allows developers to collect results in any standard container (e.g., std::vector), avoiding the overhead of proprietary result objects. Finally, a getStatistics function exposes internal structural metrics, including tree height, node counts, and memory footprint, facilitating transparent benchmarking. All indexing structures of Indexicon are designed to reside entirely within main memory. This design focuses on ultra-low latency in-memory traversal over disk I/O, recognizing that I/O is no longer the primary performance bottleneck in modern commodity hardware [1, 13, 29, 36]. Similar to other existing spatial libraries [3, 23, 25, 56, 64], our implementation operates on a singlethreaded execution model. This provides sufficient throughput for typical workloads and yields lean, highly-readable search performance for typical spatial search tasks. These deterministic execution paths currently serve as excellent raw performance baselines and embeddable components for spatial execution engines. Extending our library to fully support multi-threaded execution is a primary objective for our future work.

3.2

Spatial indexing

The current implementation of Indexicon includes the most popular tree-based spatial indices for low-dimensional points and minimum bounding boxes (MBBs), which support the filter step of spatial queries. We describe these data structures and how they are implemented within Indexicon. R-tree. Our implementation is an N-dimensional index supporting both point and MBB data. It natively supports decoupled maximum capacities (fanouts) for internal nodes and leaf nodes, enabling developers to independently optimize cache alignment and structural

depth. Its bulk-loading mechanism mirrors the packing strategy [22] adopted by the Boost Geometry library [3]. Instead of relying on rigid bottom-up sort-tile-recursive scheme [30], it constructs the tree top-down utilizing a recursive KD-tree-like bisection. At each step, it identifies the longest spatial axis of the bounding box and employs a median selection algorithm to evenly divide the records. Insertions are implemented based on the R*-tree methodology [4] featuring a forced re-insertion mechanism. When a node overflows, rather than splitting it immediately, the index temporarily removes a fraction (30% by default) of its entries farthest from the node center and re-inserts them from the root to continuously refine the overall tree structure. If a node must split, the index comprehensively evaluates all dimensions, computes the margin sums for every possible partition, and selects the axis that minimizes the total margin. Finally, deletions handle structural underflow by dissolving sparse nodes, gathering their remaining entries as orphans, and recursively reinserting them. Quad-tree & variants. Our implementation of the Quad-tree is a 2D structure for point data with bucket leaves. We developed it with three possible splitting strategies. The most popular strategy, followed by the point region (PR) Quad-tree [57], divides each overflowing node at the geometric midpoint of its bounding box, producing four spatially equal quadrants. The pseudo-median strategy [47] splits using the independent medians of the x and y axes. Finally, the point longest-axis strategy splits along the median of the longest span while using the geometric midpoint for the other axis. Bulk-loading constructs the tree top-down using a divide-andconquer approach. Starting with the global bounding box and the full set of points, the algorithm computes a split point according to the chosen strategy and creates four child nodes. The dataset is then partitioned into four and the process is recursively applied to each partition and child node, terminating only when the number of objects in the partition does not exceed the leaf node capacity threshold, at which point the partition becomes a leaf. All Quad-tree variants handle extreme data skew by allowing overflowing leaves when numerous data objects have identical coordinates, instead of recursing infinitely. An optional maximum depth limit can be imposed, if needed for an application, though our experiments show that the tree naturally stops subdividing once buckets fall below capacity, making an artificial limit unnecessary. To support data in a dynamic spatial domain, where minimum and maximum coordinates in each dimension are not fixed, dynamic insertions expand the tree via an automatic re-rooting mechanism. Whenever a new point falls outside the spatial domain currently covered by the tree, the index generates a new root that expands the spatial domain in the direction of the outlier. The entire existing tree is demoted to become one of the four child quadrants of this new root, while the remaining three siblings are initialized as empty nodes. This constant-time topological shift repeats iteratively until the bounding box of the new root fully encompasses the incoming point. Notably, while median-based strategies guarantee structural balance during bulk-loading, the PR strategy and dynamic insertions lack re-balancing mechanisms, meaning clustered data can produce long search paths. Deletion merges sibling leaves back into their parent when their combined count falls below capacity.

Indexicon: A Spatial Indexing Library

Our Oct-tree extends the PR Quad-tree decomposition to three dimensions, splitting space into eight equal octants at the midpoint of each axis. It shares the same bucket leaf design and identical coordinate duplicate handling safeguard as the 2D Quad-tree. Furthermore, it seamlessly mirrors the dynamic capabilities of the 2D structures by fully supporting re-rooting insertion for handling out of bounds points and consolidating sibling leaves upon deletion. Our MX-CIF Quad-tree is a 2D structure specialized for MBB data, which avoids data replication. Unlike the point Quad-tree, MBBs that straddle a split boundary are stored at the internal node itself rather than being pushed to a child. Straddling MBBs are maintained in sorted order along their secondary axis during bulk-loading. Nonstraddling MBBs are placed in bucket leaves, a design choice that significantly improved range query performance over the classical unbucketed layout. Bulk-loading classifies each MBB as straddling the vertical midline, straddling only the horizontal midline, or fitting entirely within one quadrant. The first two groups are stored at the current node while the quadrant groups are recursed into child nodes. Dynamic insertion also supports re-rooting for expanding spatial domains. KD-tree. Our implementation is an N-dimensional spatial index designed for point data, featuring a bucket leaf architecture. It is implemented as a binary space partitioning tree where each internal node splits the spatial domain along a single axis-aligned hyperplane. During bulk-loading, the index rapidly builds a balanced structure by recursively selecting a splitting dimension and cracking [26] the dataset at the median coordinate of the chosen split axis. This recursive in-place partitioning continues until the number of points falls below the predefined node capacity, at which point a bucket leaf is instantiated to store those records. The dimension selection process is controlled by a compile-time configuration that offers three distinct strategies. By default, the index uses an adaptive approach that dynamically calculates the spatial spread of the data points across all dimensions and splits along the axis exhibiting the widest spatial extent [20], actively mitigating the structural impact of skewed data distributions. Alternatively, this can be toggled to a round-robin strategy which cycles through the dimensions based on the current tree depth, or a longest-axis strategy that simply splits the widest dimension of the node’s geometric bounding box. Dynamic insertions traverse the established splitting hyperplanes to map the incoming point directly to the appropriate bucket leaf. If an insertion causes the bucket to exceed its maximum capacity, the leaf immediately splits along a selected dimension, extending the binary hierarchy downward. It should be noted that, unlike bulk-loading, sequential insertions do not perform global rebalancing; consequently, highly skewed insertion workloads may eventually degrade the tree’s structural balance. Finally, deletions operate by executing a standard point lookup and performing a linear scan within the matching bucket leaf to securely erase the targeted record. While the index avoids the computational overhead of global tree restructuring, it actively mitigates underflow. Specifically, if two sibling leaves experience enough deletions that their combined element count falls below the node capacity, they are merged back into their parent, converting it back into a single bucket leaf.

Visualization. Figure 1 visualizes the leaf-level spatial partitions generated by Indexicon’s indices, executed on a 100K-point randomly drawn sample of the OSM dataset with a node capacity of 128. For the R-tree, the top-down packing strategy yields tightly grouped, minimally overlapping bounding boxes resulting in a highly compact structure of 782 leaves. In contrast, dynamic R*tree insertions produce more irregular, overlapping bounds with minimal margins, expanding the tree’s footprint to 1,140 leaves. The Quad-tree variants illustrate the difference between the strict, geometrically uniform quadrants of the Point-Region (PR) strategy (which generates the most fragmented space at 2,098 leaves) and the tighter, data-driven bounds of the Pseudo Median (1,654 leaves) and Longest Axis (1,996 leaves) techniques. Finally, the KD-tree visualizations highlight the structural mechanics of binary space partitioning. Because they strictly halve the data, all three KD-tree variants generate 1,024 leaves. However, the visualization demonstrates how the Adaptive and Longest Axis strategies conform to the spatial spread of the data better than the alternating splits of the Round Robin approach.

3.3

Spatial query processing

All indices share the same range query algorithm: a recursive descent that, at each internal node, prunes children whose bounding region2 does not intersect the query. When the query’s MBB fully encloses a node’s bounding region, all data items in the subtree are scanned and reported without comparisons, thus eliminating redundant computations in large-area queries. In the MX-CIF Quadtree, for each visited internal node all data items in its straddle list are compared to the query range. The 𝑘-nearest neighbor (𝑘NN) search in all indices follows a best-first traversal. The algorithm maintains a priority queue of unvisited nodes ordered by their minimum squared distance to the query point, together with a max-heap containing the current 𝑘 best candidate neighbors. At each step, the nearest unvisited node is removed from the node queue. If its minimum distance is no smaller than the distance of the current 𝑘-th nearest candidate, the search terminates, since all remaining queued nodes are at least as far. Otherwise, leaf entries are scanned and the candidate heap is updated. For internal nodes, children whose minimum distance can improve the current result are inserted into the node queue. In the MX-CIF Quad-tree, visited internal nodes additionally scan their straddle lists during traversal.

Comparative Study

In this section, we experimentally compare the spatial indices in our Indexicon library with their most popular and best-performing open-source implementations. We first present the datasets and queries in our tests, then describe the competitors, and finally present the experimental results. All experiments were conducted on a workstation running Ubuntu 24.04.3 LTS, equipped with an Intel Core i7-14700K processor (33 MB L3 cache) and 128 GB of main memory. All codes are in C++ and compiled using GCC version 13.3.0 with the -O3 optimization flag. All datasets, spatial indices, and query workloads reside entirely in main memory. 2 For Quad-trees and KD-trees each node stores an MBB for all data in its subtree.

Simatis et al.

R-tree (Packing)

Quad-tree (PR)

R-tree (R* Insert)

KD-tree (Round Robin)

Quad-tree (Pseudo Median) Quad-tree (Longest Axis)

KD-tree (Longest Axis)

KD-tree (Adaptive)

Figure 1: The leaf MBBs generated across our various indexing strategies, executed on a 100K point sample of OSM dataset.

MARINE

MIAMI

OSM

TAXIS

TIGER

TORONTO

Figure 2: Spatial distribution of the datasets used in our evaluation projected onto their first two dimensions, with point and MBBs of geometries plotted in green and red, respectively Table 2: Dataset statistics and structural profiles Dataset

Records

MARINE MIAMI OSM TAXIS TIGER TORONTO

25.0M 3.5M 103.5M 112.8M 17.9M 21.6M

4.1

Type Point MBB→Point Point Point MBB→Point Point

Size

Dims

Dupl.

Description

716.2 MB 312.2 MB 2.0 GB 2.2 GB 715.2 MB 679.5 MB

3D 3D→2D 2D 2D 2D 3D→2D

0.01% 0.02% 0.03% 14.55% 5.60% 6.94%

US coastal vessel tracking data Urban traffic-object MBBs in Miami Geolocations in Central America NYC Taxi pickup geolocations Lower 48 street MBBs Toronto urban LiDAR point cloud

Experimental setup

Datasets. We use six real-world datasets spanning various geographic applications and data types; Table 2 lists their statistics and Figure 2 visualizes them. Tailored for spatial and spatiotemporal applications, our evaluation focuses on 2D and 3D domains. • MARINE [9]: Contains Automatic Identification System (AIS) spatiotemporal (i.e., 3D) tracking data for vessels in US coastal waters, characterized by trajectories clustered along shipping lanes. • MIAMI [70]: Contains 3D MBBs of annotated traffic objects in Miami, such as a vehicle, cyclist, or pedestrian. • OSM [46]: Contains 2D spatial points in Central America from OpenStreetMap. • TAXIS [15]: Captures 2D spatial points representing NYC taxi pickup locations, exhibiting hotspots in dense urban zones.

• TIGER [10]: Consists of 2D MBBs tracking local street centerlines across the contiguous United States. • TORONTO [62]: A dense and highly clustered 3D LiDAR point cloud dataset capturing urban roadways in Toronto, Canada.

To conduct standardized 2D point benchmarking across the entire collection, we derive a 2D point representation from each dataset by retaining only its first two coordinates. For originally 3D point datasets, this corresponds to projecting each point onto its first two dimensions. For MBB datasets, we use the first two coordinate attributes to obtain representative 2D points. This gives us a uniform 2D point workload while preserving the original data sources and spatial distributions. Benchmark workload. Unless stated otherwise, we evaluate bulkloading and maintenance in a single mixed workload. We randomly bulk-load 80% of each dataset, insert the remaining 20% sequentially, and then delete 5% of the records. This models a common setting where an index is first built over historical data and later maintained under incoming updates, with deletions occurring less frequently. For methods without bulk-loading support (Table 1), we build the initial 80% by one-by-one insertions and report the cumulative insertion time as the bulk-loading cost. Queries. We generate 1,000 queries for each query type, including range, and 𝑘-nearest neighbor (𝑘NN) queries. For this, we randomly

Indexicon: A Spatial Indexing Library

sample points without replacement directly from the dataset, ensuring the query workload follows the underlying data distribution. For 𝑘NN queries, these are used as query points, and we vary 𝑘 in {1, 10, 100}. Range queries are formulated as axis-aligned hyperrectangles with side lengths proportional to the domain extent of each respective dimension, using as geometric centers a fresh random sample of dataset points. We configure their extents to cover 0.01%, 0.1%, and 1.0% of the domain at each axis. Finally, we report the total execution latency per query setting. Competitors. We select the competitors according to their ability to handle our workload. Therefore, we compare Indexicon against the closest usable implementation for each index family. For the R-tree, we consider Boost Geometry, since it supports the full mixed workload: bulk-loading, insertions, deletions, range queries, and 𝑘NN search. We do not consider GEOS’s STR-tree because it is immutable after construction and supports only 1-NN search. Furthermore, we do not consider LibSpatialIndex because its disk-oriented architecture makes it less representative of the lightweight mainmemory setting evaluated here; a previous evaluation in [35] also demonstrated that Boost R-tree outperforms LibSpatialIndex R-tree. For point Quad-trees and MX-CIF Quad-trees over MBBs, we consider GEOS, applying the required post-filtering step to obtain exact range-query results. For 3D point indexing, we consider PCL’s Octtree. However, due to its single-precision representation, we only consider PCL for range-search experiments and exclude it from 𝑘NN comparisons. For KD-trees, we consider Nanoflann, evaluating its dynamic adaptor since we assume non-static workloads. We exclude CGAL because its indices lack on maintenance, and its Orth-tree reports intersected leaves rather than exact objects. We also exclude Vigier’s Quad-tree because it requires a fixed global domain at initialization, and does not support 𝑘NN search.

4.2

R-tree benchmark

In the first set of experiments, we investigate how parameter choices (node capacity, percentage of removed entries at forced reinsert) affect the performance of the two R-tree implementations. Then, we compare Indexicon and Boost R-tree implementations in construction and update costs as well as in query performance. 4.2.1 Effect of parameters. An important parameter in R-tree configuration is the maximum node capacity (or fanout), which dictates the maximum number of entries a node can hold. While Indexicon natively supports setting distinct capacities for internal nodes and leaves, allowing developers to optimize for different cache-line alignments, Boost’s R-tree enforces a single capacity for both. To ensure a fair comparison, we constrain Indexicon to use identical capacities for both node types in this experiment. We ran this experiment with a workload of 80% bulk-loading and 20% insertions. Figure 3 visualizes the performance impact of varying the node capacity from 32 to 512 across our datasets. The results highlight an inherent trade-off between construction speed, insertion scalability, and query efficiency for both implementations. Importantly, Indexicon consistently outperforms Boost across all configurations. Figure 3a shows that increasing the node capacity accelerates bulkloading. A higher capacity yields a shallower tree with fewer nodes in total, significantly reducing memory allocation overhead and recursions during packing. Conversely, dynamic insertion (Figure 3b)

scales poorly with larger capacities. High-capacity nodes incur a heavier penalty during inserts, as the algorithms must evaluate larger arrays to select the optimal subtree, and perform more extensive memory shifts during node overflows. Finally, Figure 3c demonstrates that spatial search benefits from medium node sizes. Larger capacities consolidate data into fewer, contiguous blocks of memory, minimizing tree depth and cache misses during traversal. Across all datasets, the 0.1% range query latencies drop significantly as capacity increases, though the performance gains begin to degrade or plateau beyond a capacity of 128 for multiple datasets (e.g., TIGER). This degradation occurs because large nodes force the query to linearly scan irrelevant entries within the leaves, offsetting the benefits of a shallower tree. Thus, we select capacity 128 as the default value for the rest of our R-tree benchmark. Next, we explore the efficacy of forced re-insertion on 2D point data. In the R*-tree, when a node overflows, the index temporarily removes a predefined fraction of elements farthest from the node center and re-inserts them from the root to refine the tree structure. Like in the capacity experiment, the selected workload consists of 80% bulk-loading and 20% insertions3 . Figure 4 illustrates the impact of varying the re-insertion percentage from 0% up to 50% on dynamic insertion and 0.1% range query times. These behavioral trends were verified across both our Indexicon and Boost, with our implementation consistently maintaining superior performance across all configurations. The results reveal that increasing the reinsertion percentage imposes a severe penalty on insertion latency. On OSM, disabling re-insertion (i.e., 0%) yields an insertion time of 36.04 secs, whereas utilizing the historically accepted 30% nearly quadruples the time to 131.95 secs. Conversely, the anticipated improvements in query execution times are marginal and highly inconsistent. As observed in Figure 4b, the query times exhibit slight fluctuations rather than demonstrating a smooth, monotonic improvement as the re-insertion rate increases. This disconnect stems from the architectural shift from disk-bound to main-memory systems. The 30% heuristic was originally optimized for magnetic disks, where spending CPU time during insertions to improve tree structure was justified if it saved disk reads during a query. However, for an in-memory framework, burning CPU cycles to re-insert entries causes huge insertion delays, while the structural improvements result in negligible time-savings of memory traversal. The most significant drop in query time occurs on MARINE where it falls from 200.35 msecs (at 0%) to 185.94 msecs at a 10% reinsertion rate, but pushing the rate higher yields no benefit. Meanwhile, on datasets like TIGER, query performance remains effectively static (fluctuating trivially between 2.80 msecs and 2.89 msecs). Given the extreme computational cost incurred during insertions and the unpredictable, trivial returns observed during search operations, we conclude that the historically empirical standard of 30% forced re-insertion is highly detrimental for modern workloads. Thus, we advocate for keeping re-insertion either strictly disabled (0%) or limited to small fractions (e.g., 10%, as the default) for the remaining experiments. 4.2.2 Comparing R-tree implementations. We now compare the performance of Indexicon’s R-tree against the Boost Geometry 3We repeated the experiment with a fifty-fifty split between bulk-loading and insertions

and observed similar results.

Simatis et al.

Boost R-tree

Bulk Load Time (s)

MARINE

2.6

MIAMI

0.275 2.4 0.250 0.225 2.2 0.200 32 64 128 256 512 32 64 128 256 512

Node Capacity

Indexicon R-tree

OSM

TAXIS 14 13 12

8 7 6

Node Capacity

32 64 128 256 512

TIGER

1.0

Node Capacity

2.0

TORONTO

1.8

1.2 32 64 128 256 512

Node Capacity

1.4

1.6 32 64 128 256 512

32 64 128 256 512

Node Capacity

Insert Time (s)

(a) Bulk-loading

MARINE

30 20 10

32 64 128 256 512

10.0 7.5 5.0 2.5

Node Capacity

MIAMI

300

Boost R-tree

Indexicon R-tree

OSM

TAXIS 200

200 32 64 128 256 512

100

Node Capacity

100 32 64 128 256 512

TIGER

40 30 20

32 64 128 256 512

Node Capacity

TORONTO 40 30 20

32 64 128 256 512

Node Capacity

32 64 128 256 512

Node Capacity

(b) Dynamic insertions

Query Time (ms)

Boost R-tree 400

MARINE

MIAMI 5

300

200 32 64 128 256 512

32 64 128 256 512

Node Capacity

60 50 40 30

Node Capacity

Indexicon R-tree

OSM

TAXIS 60 50 40

32 64 128 256 512

Node Capacity

TORONTO 35 30 25

4 32 64 128 256 512

Node Capacity

TIGER 5

32 64 128 256 512

Node Capacity

32 64 128 256 512

Node Capacity

Figure 3: Impact of R-tree node capacity on bulk-loading, dynamic insertions, and range query performance; workload 80% of each dataset bulk-loaded, 20% insertions and 1000 queries

Boost R-tree

Insert Time (s)

MARINE

10 5

MIAMI

2 0 10 20 30 40 50

Re-insertion (%)

0 10 20 30 40 50

Re-insertion (%)

OSM 150 100 50

Indexicon R-tree 150

TAXIS

100 50 0 10 20 30 40 50

Re-insertion (%)

0 10 20 30 40 50

Re-insertion (%)

TIGER

TORONTO

0 10 20 30 40 50

Re-insertion (%)

Query Time (ms)

(a) Dynamic insertions Boost R-tree Indexicon R-tree

MARINE

MIAMI

OSM

TAXIS

TIGER

TORONTO

Re-insertion (%)

3.2 40.0 27.5 3.8 45 37.5 250 25.0 3.0 3.6 35.0 40 22.5 3.4 200 32.5 2.8 35 0 10 20 30 40 50 0 10 20 30 40 50 0 10 20 30 40 50 0 10 20 30 40 50 0 10 20 30 40 50 0 10 20 30 40 50 (b) Range queries of 0.1% extent

Figure 4: Impact of R-tree forced re-insertion percentage on 2D point datasets; workload 80% of each dataset bulk-loaded, 20% insertions and 1000 queries

Indexicon: A Spatial Indexing Library

Table 3: R-tree packing, dynamic insertion and deletion times; default workload Boost R-tree Dataset

Indexicon R-tree

Build (s) Insert (s) Delete (s) Build (s) Insert (s) Delete (s)

2D point MARINE MIAMI OSM TAXIS TIGER TORONTO

2.34 0.24 7.14 13.22 1.20 1.78

11.20 3.08 91.10 77.16 13.30 14.33

3.22 0.21 9.01 9.81 1.08 1.51

2.34 0.23 6.78 13.18 1.16 1.72

9.05 2.51 77.16 62.40 11.24 11.53

1.76 0.17 7.59 8.62 0.94 1.21

2.26 0.30 2.06

20.30 3.75 19.52

1.91 0.24 2.43

2.22 0.25 1.88

17.75 3.24 17.72

1.73 0.21 1.79

0.26 1.25

2.71 10.88

0.35 2.18

0.26 1.24

2.00 7.71

0.35 1.91

0.28

4.66

0.40

0.28

2.52

0.39

3D point MARINE MIAMI TORONTO 2D MBB MIAMI TIGER 3D MBB MIAMI

Querying MBB datasets. For 2D MBB data, Figure 7 shows that Indexicon consistently outperforms Boost for both range and 𝑘NN queries. On TIGER, Indexicon evaluates the 1.0% range queries in 39.38 msecs compared to Boost’s 46.38 msecs, while on MIAMI, it requires 39.29 msecs compared to Boost’s 48.90 msecs. The same trend appears for 𝑘NN search, where Indexicon benefits from its lightweight node representation. For example, for 𝑘 = 100, Indexicon takes 17.35 msecs on TIGER and 10.86 msecs on MIAMI, compared to Boost’s 20.36 msecs and 13.23 msecs, respectively. For 3D MBB data, Figure 8 shows an even larger performance gap since the additional dimension increases the cost of boundingbox comparisons. Indexicon remains faster across all query settings: for the 1.0% range queries on MIAMI, it finishes in 56.78 msecs, while Boost requires 116.49 msecs, yielding roughly a 2× speedup. The advantage is also visible for smaller ranges, e.g., 7.68 msecs versus 11.90 msecs for the 0.10% queries. For 𝑘NN queries, Indexicon again maintains a consistent lead; for 𝑘 = 100, it takes 12.14 msecs compared to Boost’s 14.98 msecs. Overall, Indexicon exceeds search performance of Boost Geometry due to its structural quality, while offering a much simpler open-source codebase.

4.3 R-tree across all datasets. The evaluation is conducted using the default mixed workload. We break down the analysis by data type and dimensionality. Table 3 details the construction and maintenance latencies per object type and dimensionality. Across the board, Indexicon matches or surpasses Boost Geometry’s performance in bulk-loading. While both libraries utilize the same underlying packing strategy, Indexicon’s lightweight node structure and avoidance of deep abstraction layers yield a slight edge in bulk-loading speeds. Indexicon’s R-tree is significantly faster in dynamic insertions. As expected, dynamic insertions are much more expensive than bulk-loading, so the large performance gap between the two structures gives Indexicon a big advantage over Boost in the overall construction cost. Deletions follow the same trend. Indexicon is consistently faster than Boost in nearly all settings, with the only tie occurring on 2D MBBs from MIAMI. These results indicate that Indexomicon’s architecture benefits both construction and index maintenance. Querying point datasets. Figure 5 shows the performance of the two indices in spatial range and 𝑘-nearest neighbor (𝑘NN) queries on 2D point data. Indexicon scales well as the query expands, outperforming Boost in all settings. For instance, on OSM’s 1.0% range queries, Indexicon executes the 1000 queries in 832.25 msecs, comfortably outperforming Boost’s 1124.23 msecs execution time. This demonstrates that Indexicon’s contiguous memory layouts and data locality directly translate to superior cache utilization during spatial scans. Figure 6 visualizes the execution times for both 3D range and 𝑘NN queries. The scaling advantages observed in 2D remain prominent in higher dimensions. On MARINE, Indexicon resolves 1000 queries of 1.0% extent in 239.31 msecs versus Boost’s 265.34 msecs. For 𝑘NN performance, Indexicon continues to retrieve neighbors faster. For example, for 𝑘 = 100 on TORONTO, Indexicon pulls the targets in 15.57 msecs, outperforming Boost’s 21.03 msecs.

Quad-tree and Oct-tree benchmark

We now turn our focus to the Quad-tree and Oct-tree implementations. Before comparing Indexicon implementations to other libraries, we test the effect of the three partitioning strategies in Indexicon. 4.3.1 Effect of partitioning and parameters. We evaluate three spacepartitioning strategies under varying maximum tree depth constraints (4, 8, 16, and unlimited). The evaluated strategies (discussed in detail, in Section 3.2) are: (1) the classic Point-Region (PR) Quadtree which divides space into equal quadrants, (2) the Pseudo Quadtree which splits at a synthetic coordinate consisting of the independent medians of both dimensions, and (3) a Point Quad-tree variant that splits on the physical median along the longest axis. We experiment with a workload which packs 80% of the dataset into the index and inserts the rest. Figure 9a demonstrates the PR Quad-tree is the fastest structure to construct, while the point longest-axis strategy has an advantage over pseudo-median. For instance, at unlimited depth in OSM, point longest-axis completes bulk-loading in 10.01 secs compared to 11.61 secs for pseudo-median. This speedup is caused by the 𝑂 (1) axispruning selection which results in a single linear-time pass per split, cutting the split-finding in half relative to the dual-axis approach of pseudo-median. Dynamic update times shown in Figure 9b present no clear winner. In general, the PR Quad-tree is the fastest version for unlimited depth. Figure 9c reveals that imposing a strict maximum depth constraint heavily penalizes query performance regardless of the splitting strategy. A maximum depth of 4 is a particularly bad choice, creating big leaves that effectively degrade spatial indexing into linear scan. Under such severely truncated depth bounds, the medianbased strategies perform best, as their splits balance the data distribution, maximizing the partitioning utility of the few available tree levels. For example, pseudo-median executes the 0.1% range queries on OSM in 1427.81 msecs, compared to 3341.39 msecs for point longest-axis and 3576.93 msecs for the PR Quad-tree. However, as

Simatis et al.

Query Time (ms)

Boost R-tree

MARINE

103

MIAMI

103

101

102 0.010 0.10

100

1.0

Query Extent (%)

OSM

0.010 0.10

Indexicon R-tree

102

101

1.0

0.010 0.10

Query Extent (%)

TAXIS

103

1.0

TIGER 101

102 101

0 1.0 10 0.010 0.10

0.010 0.10

Query Extent (%)

TORONTO

103

Query Extent (%)

1.0

0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

(a) Range queries varying extent

Query Time (ms)

Boost R-tree

MARINE

OSM

100

k (Nearest Neighbors)

TAXIS

5 0

MIAMI

Indexicon R-tree

100

k (Nearest Neighbors)

100

k (Nearest Neighbors)

TIGER

10 5

100

k (Nearest Neighbors)

TORONTO

10 5

100

k (Nearest Neighbors)

100

k (Nearest Neighbors)

(b) 𝑘NN queries varying 𝑘

Figure 5: Query performance on 2D point datasets; default workload

Query Time (ms)

MARINE

MIAMI

101

102

Indexicon R-tree

TORONTO 102

101 1.0

0.010 0.10

Query Extent (%)

1.0

0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

100

k (Nearest Neighbors)

100

k (Nearest Neighbors)

TIGER 101 0 1.0 10 0.010 0.10

1.0

Query Extent (%)

(a) Range queries varying extent

TORONTO

MIAMI

Query Extent (%)

Indexicon R-tree

MIAMI

Boost R-tree

Query Time (ms)

Boost R-tree

Indexicon R-tree

100 0.010 0.10

(a) Range queries varying extent

MARINE

Boost R-tree

101

100 0.010 0.10

Query Time (ms)

Boost R-tree

MIAMI

100

(b) 𝑘NN queries varying 𝑘

5 0

TIGER

k (Nearest Neighbors)

Indexicon R-tree

100

k (Nearest Neighbors) k (Nearest Neighbors) (b) 𝑘NN queries varying 𝑘

Figure 6: Query performance on 3D point datasets; default workload

the depth limit is relaxed (e.g., to 16) or left uncapped, this structural skew disappears, and the range query times of all methods converge. Since query performance smooths out when artificial truncation is removed, and the PR Quad-tree is superior in construction and insertion efficiency, we adopt the unconstrained PR Quad-tree as our default configuration for the remainder of this paper. 4.3.2 Comparing Quad-tree and variants implementations. Point datasets. We compare the PR Quad-tree and MX-CIF of Indexicon against GEOS Quad-tree. We subject both indices to the default workload. Table 4 reports construction and deletion performance for GEOS and Indexicon’s Quad-trees on point data. GEOS exhibits fast insertions because its MX-CIF Quad-tree follows a different

Figure 7: Query performance on 2D MBB datasets; default workload insertion policy from Indexicon’s capacity-driven bucket Quadtrees. In Indexicon’s PR Quad-tree, an overflowing leaf is split and its records are redistributed, which may create many additional nodes for dense or skewed point distributions. GEOS, instead, inserts items into the smallest existing or newly created quad that contains their envelope and allows nodes to store item lists directly. For point data, whose envelopes have zero area, GEOS also pads the envelope and uses a special insertion rule to avoid recursively creating deeper quads for zero-width envelopes. This limits subdivision and can lead to much shallower trees. For example, on MARINE, GEOS and Indexicon’s PR Quad-tree consist of 10 and 25 levels, respectively. Within Indexicon, MX-CIF Quad-tree often inserts faster than the PR Quad-tree because it can stop earlier during insertion. Both

Indexicon: A Spatial Indexing Library

all records in leaf buckets and avoids the additional scans over internal-node straddle lists required by MX-CIF.

Table 5: Oct-tree bulk-loading and dynamic insertion times on 3D point datasets; workload 80% of each dataset bulkloaded, 20% insertions

102

101

101 0.010 0.10

Query Time (ms)

Boost R-treeR-treeBoost Indexicon Indexicon R-treeR-tree Indexicon R-tree MIAMI 2 MIAMI MIAMI

Query Time (ms)

Boost R-tree

0.010 0.10

1.05

Query Extent (%)

1.0

Query Extent (%)

(a) Range queries varying extent

100

k (Nearest Neighbors)

(b) 𝑘NN queries varying 𝑘

Figure 8: Query performance on 3D MBB data; default workload Table 4: Quad-tree variants bulk-loading, insertion, and deletion times on 2D point datasets; default workload Build (s) Dataset MARINE MIAMI OSM TAXIS TIGER TORONTO

GEOS

Insert (s) MX GEOS

1.73 2.15 3.87 0.36 0.16 0.31 - 7.25 13.82 - 10.11 19.93 0.86 0.82 1.68 1.44 1.58 2.94

Build (s)

Delete (s) MX GEOS PR MX

0.85 6.08 4.80 370.86 1.85 7.66 0.24 0.23 0.25 0.20 0.10 0.13 - 18.65 17.16 - 5.65 7.47 - 17.90 17.26 - 5.82 6.67 0.63 1.76 1.70 73.32 0.65 0.87 0.81 2.53 2.40 72.78 0.91 0.96

variants split overflowing leaves and redistribute records, but MXCIF may retain records at internal nodes when they lie on splitting axes. This reduces the number of leaf-level insertions and produces slightly fewer leaves. On OSM, after deletion, the PR Quad-tree contains 2.01M leaves compared with 1.99M leaves for MX-CIF. Thus, MX-CIF Quad-tree insertions often terminate slightly earlier. However, GEOS’s design can hurt deletions. Since many records may accumulate in node-local item lists, deleting an item may require searching through relatively large lists after the candidate node has been found. In contrast, Indexicon’s capacity-based Quadtrees keep leaf buckets bounded, so deletion searches are usually over smaller local containers, although the tree may be deeper. This trade-off is visible on TIGER where deletion took 0.65 secs with Indexicon’s PR Quad-tree, but 73.32 secs with GEOS. GEOS also failed to complete on OSM, while TAXIS was terminated due to excessive runtime. Figure 10 visualizes the range query execution times. The GEOS Quad-tree query operates as a primary filter, returning coarse candidate items whose spatial cells overlap the search window. To guarantee exact results, post-filtering is applied. This post-filtering, combined with the necessity to iterate through midline-straddling items, drastically degrades query performance. On the 1.0% range queries for MARINE, the Indexicon PR Quad-tree resolves the query in 2,07 secs, outpacing GEOS, which struggles at 33,8 secs. Overall, the strict capacity constraints and bucketed leaves of the Indexicon’s Quad-trees provide reliable construction and superior query and deletion throughput. Among the Indexicon variants, PR and MX-CIF Quad-trees exhibit comparable range-query performance, but PR has a clear advantage for 𝑘NN queries because it stores

Insert (s)

Dataset

PCL

Indexicon

PCL

Indexicon

MARINE TORONTO

1.28 0.70

2.75 2.48

0.87 1.24

3.63 3.26

Table 5 reports construction and insertion times for the Indexicon Oct-tree and the PCL Oct-tree on 3D point datasets. PCL demonstrates faster build times because its Oct-tree relies on a resolution-driven, voxel-based architecture. Instead of storing full point records within the tree structure, its leaves store indices referencing the original point cloud array. This compact point-to-voxel mapping makes insertions highly efficient but hurt query performance. We enable PCL’s dynamic-depth mode to enforce a leaf capacity limit, mimicking Indexicon’s splitting behavior. However, this mechanism remains fundamentally bounded by PCL’s maximum tree depth, which is dictated by the initial spatial resolution. In contrast, Indexicon’s Oct-tree is a capacity-driven spatial index: overflowing leaves are split and their records are redistributed as part of the index structure. Thus, Indexicon performs more structural maintenance during construction and insertion, whereas PCL prioritizes a lightweight, index-only insertion path. In range queries (Figure 11), Indexicon has a large performance advantage over PCL. This is because PCL’s lightweight insertion strategy takes a toll on query evaluation. First, PCL’s index-based storage imposes a significant overhead due to indirect memory accessing; to evaluate exact bounds, candidates returned by a leaf node require random memory lookups into the external point array, leading to frequent CPU cache misses. Second, since PCL natively indexes data using 32-bit floats, to avoid false negatives, the query box must be artificially expanded in float space, and all candidates returned by PCL must be post-filtered against the exact 64-bit coordinates. By avoiding both indirect memory accesses and postfiltering, Indexicon achieves substantially higher query throughput. On the 1.0% MARINE queries, the Indexicon Oct-tree is 63× faster than PCL. On TORONTO, the difference is smaller, around 4×, but still significant. Table 6: MX-CIF Quad-tree bulk-loading, dynamic insertion and deletion times on MBB datasets; default workload Build (s)

Insert (s)

Delete (s)

Dataset

GEOS

Indexicon

GEOS

Indexicon

GEOS

Indexicon

MIAMI TIGER

0.22 2.30

0.29 1.74

0.17 2.21

0.16 1.60

0.28 1.60

1.34 4.29

MBB datasets. To evaluate indexing performance on MBB data, we compare the Indexicon MX-CIF Quad-tree against the GEOS MX-CIF Quad-tree under the default workload. Table 6 reports construction and dynamic maintenance times for the MBB datasets.

Simatis et al.

Bulk Load Time (s)

Pseudo Quad-Tree

MARINE

MIAMI

0.3

0.1

Max Depth

Insert Time (s)

0.04 0.03 0.02 0.01 4

2 1 4

MIAMI

Max Depth

1.5

1.0

MARINE

Query Time (ms)

104

MIAMI

102

103

OSM

101 4

Max Depth

TORONTO

0.4 0.2

0.1

Max Depth

TAXIS

Max Depth

Point Quad-tree

TIGER

103 102

Max Depth

0.3 4

Max Depth

104

102 4

Max Depth

TIGER 0.1

PR Quad-Tree

103

Point Quad-tree

(b) Dynamic insertions

Pseudo Quad-Tree

0.2 4

Max Depth

TORONTO

2.5 2.0 1.5 1.0

Max Depth

TAXIS

15 10 5

1.0

0.5 4

PR Quad-Tree

1.5

Max Depth

(a) Bulk-loading

OSM

Max Depth

TIGER

Max Depth

Pseudo Quad-Tree

MARINE

Point Quad-tree

TAXIS

10 8 6

0.2

PR Quad-Tree

OSM

TORONTO

102

103

101

102

Max Depth

Query Time (ms)

Figure 9: Impact of Quad-tree maximum depth constraints and splitting strategy construction and query performance; workload 80% of each dataset bulk-loaded, 20% insertions and 1000 queries

MARINE

GEOS Quad-tree

Indexicon MX-CIF Quad-tree

MIAMI

OSM

102

103

101

102

100

101

0.010 0.10

1.0

Query Extent (%)

0.010 0.10

1.0

Query Extent (%)

0.010

0.10

TAXIS

103

104

1.0

Query Extent (%)

Indexicon PR Quad-tree

TIGER 101

0.010

0.10

1.0

0.010 0.10

Query Extent (%)

TORONTO

104 103 102 101

103

1.0

0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

(a) Range queries varying extent

Query Time (ms)

Indexicon MX-CIF Quad-tree

MARINE

MIAMI

101

101 100

0 100 10

k (Nearest Neighbors)

OSM

101

0 100 10

k (Nearest Neighbors)

Indexicon PR Quad-tree

TAXIS

101

0 100 10

k (Nearest Neighbors)

TIGER

101

0 100 10

k (Nearest Neighbors)

TORONTO

101

0 100 10

k (Nearest Neighbors)

100

k (Nearest Neighbors)

(b) 𝑘NN queries varying 𝑘

Figure 10: Query performance on 2D point datasets; default workload Indexicon is consistently faster during insertions, whereas GEOS

is faster during deletions. For example, on TIGER, Indexicon completes insertions in 1.60 secs and deletions in 4.29 secs, while GEOS

Indexicon: A Spatial Indexing Library

Query Time (ms)

PCL Oct-tree

Indexicon Oct-tree

MARINE

103 102 101

Table 8: KD-tree bulk-loading, dynamic insertion and deletion times on point datasets; default workload

TORONTO 103 102 101

0.010 0.10

1.0

Nanoflann Dataset

0.010 0.10

Query Extent (%)

2D point

1.0

Query Extent (%)

Figure 11: Query performance on 3D point datasets; workload 80% of each dataset bulk-loaded, 20% insertions

Query Time (ms)

GEOS Quad-tree

MARINE MIAMI TORONTO

TIGER

102

1 1.0 10 0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

Figure 12: Query performance on MBB datasets, range queries varying extent; default workload requires 2.21 secs for insertions but only 1.60 secs for deletions. This difference stems from the deletion policies of the two implementations. GEOS removes the item from a node, and prunes a child only if it is empty. In contrast, Indexicon may collapse four sibling leaves back into their parent if their combined contents fit within one bucket. This local consolidation adds deletion overhead, but keeps the tree layout more compact for subsequent queries. As shown in Figure 12, Indexicon’s MX-CIF Quad-tree is significantly faster than GEOS in all cases. While GEOS needs a costly post-filtering step to eliminate false positives, Indexicon’s MX-CIF Quad-tree natively evaluates exact bounds during traversal. Furthermore, our implementation utilizes a bucketed leaf architecture for non-straddling geometries, heavily optimizing cache locality during spatial scans. These results confirm that Indexicon’s lean architecture scales efficiently for spatial extents.

KD-tree benchmark

Finally, we present our KD-tree benchmark. Before comparing Indexicon implementation against Nanoflann’s KD-tree on point datasets, we investigate the effectiveness of the three KD-tree splitting strategies supported in Indexicon. Table 7: KD-tree splitting strategies: bulk-loading and dynamic insertion times; workload 80% of each dataset bulkloaded, 20% insertions Build (s) Dataset MIAMI MARINE OSM TAXIS TIGER TORONTO

5.04 0.20 7.41 21.99 0.95 1.72

2.61 0.26 16.35 20.45 2.22 2.15

0.18 0.02 1.17 1.28 0.12 0.15

2.01 0.20 6.49 10.89 1.01 1.60

2.30 0.14 13.95 15.02 1.62 1.92

1.11 0.09 5.07 5.65 0.81 0.82

3.91 0.22 2.00

2.18 0.29 2.58

0.18 0.02 0.15

2.05 0.22 1.73

2.34 0.16 2.00

1.01 0.10 0.90

102

101 0.010 0.10

4.4

MARINE MIAMI OSM TAXIS TIGER TORONTO 3D point

Indexicon MX-CIF Quad-tree

MIAMI

Indexicon

Build (s) Insert (s) Delete (s) Build (s) Insert (s) Delete (s)

Insert (s)

Round-robin

Adaptive

Longest-axis

Round-robin

Adaptive

Longest-axis

0.24 2.11 7.05 11.61 1.14 1.72

0.27 2.51 9.06 13.61 1.48 2.19

0.21 1.95 6.49 10.76 1.06 1.59

0.15 2.11 13.54 14.72 1.60 1.83

0.15 2.17 13.85 15.14 1.62 1.87

0.14 2.14 13.94 15.20 1.57 1.83

4.4.1 KD-tree splitting strategies. We evaluate the three KD-tree splitting strategies in Indexicon: (1) the classic round-robin strategy, which cycles through the dimensions, (2) the adaptive splitting strategy, which calculates the spatial spread of the elements and dynamically splits along the widest dimension, and (3) the longestaxis approach, which determines the split by selecting each time the dimension with the largest bounding extent. We evaluate all variants using an 80% bulk-loading and 20% insertion workload. Table 7 details the construction phase. The adaptive strategy has the highest construction cost because it performs an additional scan of the records at every internal node to compute the minimum and maximum coordinate values per dimension before selecting the split axis. In contrast, both round-robin and longest-axis avoid this data scan. Round-robin selects the split dimension based on the tree depth, while longest-axis only compares the extents of the node’s already maintained bounding region. Although round-robin has the cheapest split-axis selection rule, it is slower than longest-axis during bulk-loading (e.g., 7.05 secs vs 6.49 secs on OSM). This occurs because the dominant cost of bulk-loading is the in-place median partitioning step and not the split axis selection. By blindly cycling through dimensions, round-robin frequently forces the algorithm to partition along axes where the data is tightly clustered or contains many identical values, which degrades performance. Longest-axis avoids this by always splitting along the dimension with the widest spatial spread, making it the fastest bulk-loading strategy overall. Despite the significant overhead that it imposes in the tree construction, the adaptive strategy offers minimal query performance advantage, as shown in Figure 13. This happens because our KDtree utilizes bucketed leaves. The adaptive and longest-axis splits were designed to prevent long, thin cells that degrade search performance. However, terminating the recursion early and storing elements in contiguous buckets naturally absorbs these geometric irregularities to a certain extent (see Figure 1). Consequently, we select the longest-axis strategy as the default for our framework since it usually improves query performance (see MARINE, MIAMI, and OSM), with a minimal construction overhead. 4.4.2 Comparing KD-tree implementations. We evaluate our KDtree against Nanoflann, a popular KD-tree implementation on our default workload. Table 8 details the latency of the structural modifications. It is critical to note that Nanoflann’s dynamic adaptor

Simatis et al.

Query Time (ms)

Indexicon KD-tree (Round-Robin)

MARINE

OSM

101

102 101 0.010 0.10

Indexicon KD-tree (Adaptive)

MIAMI

1.0

100

Query Extent (%)

0.010 0.10

102

101

1.0

0.010 0.10

Query Extent (%)

Indexicon KD-tree (Longest Axis)

TAXIS

1.0

TORONTO 102

101

101 0.010 0.10

Query Extent (%)

TIGER

1.0

100

Query Extent (%)

0.010 0.10

1.0

0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

Figure 13: Impact of KD-tree splitting strategies on query performance for 2D point datasets; workload 80% of each dataset bulk-loaded, 20% insertions

Query Time (ms)

Nanoflann KD-tree

MARINE

104 103 102 0.010 0.10

1.0

103 102 101 100

Query Extent (%)

MIAMI

0.010 0.10

104 103 102 101 1.0

0.010 0.10

Query Extent (%)

Indexicon KD-tree (Longest Axis)

OSM

TAXIS

104 103 102 101 1.0

101 1.0

100

Query Extent (%)

0.010 0.10

TORONTO

104 103 102 101

102

0.010 0.10

Query Extent (%)

TIGER

103

1.0

0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

(a) Range queries varying extent Nanoflann KD-tree Indexicon KD-tree (Longest Axis)

MARINE

Query Time (ms)

102

MIAMI 101

101 1

0 100 10

OSM

102 101

100

TAXIS

102

TIGER 101

101 1

100

TORONTO

102 101

0 100 10

100

(b) 𝑘NN queries varying 𝑘

Nanoflann KD-tree

Indexicon KD-tree (Longest Axis)

MARINE

MIAMI

103

101 0.010 0.10

1.0

0.010 0.10

Query Extent (%)

TORONTO

104 103 102 101

102 101 100

103

1.0

0.010 0.10

Query Extent (%)

1.0

Query Extent (%)

(a) Range query varying extent Nanoflann KD-tree Indexicon KD-tree (Longest Axis)

MARINE

102

Query Time (ms)

performs multiple bulk-loads due to its underlying forest structure. Consequently, our KD-tree achieves superior construction times, with the only exception being TIGER, where Nanoflann has a slight edge. Conversely, the deletion times show a clear performance inversion with Nanoflann being drastically faster (e.g., 1.17 secs vs 5.07 secs on OSM). This behavior is an artifact of Nanoflann’s lazy deletion strategy, which handles removals by flagging data as invalid (i.e., tombstones) without modifying the tree. While tombstones minimize structural mutation costs during writes, they shift the computational burden onto downstream reads as seen in our query experiments. Figure 14 demonstrates that our KD-tree outperforms Nanoflann by orders of magnitude across all settings in query times. For instance, on OSM’s 1.0% range query, KD-tree is roughly 60× faster than Nanoflann. This performance gap extends to 𝑘NN searches; for a 100-NN search on OSM, our method registers a latency of 6.06 msecs compared to Nanoflann’s 91.59 msecs. This is a consequence of the underlying structures and algorithmic constraints. Because our KD-tree remains a singular, cohesive tree optimized for continuous CPU cache prefetching, query traversals prune branches with maximum efficiency. In contrast, Nanoflann’s queries iterate and merge results from its underlying forest while simultaneously

Query Time (ms)

Figure 14: Query performance on 2D point datasets; default workload

MIAMI 101

101 1

0 100 10

TORONTO 101

0 100 10

100

(b) 𝑘NN queries varying 𝑘

Figure 15: Query performance on 3D point datasets; default workload

spending clock cycles processing tombstones. This structural inefficiency is severely compounded during range searches which are further hurt by post-filtering.

Indexicon: A Spatial Indexing Library

Next, we extend our evaluation to 3D point cloud data with the default workload. Table 8 highlights the construction phase. Our KD-tree maintains its speed advantage during initial bulkloading, completing the phase in 2.05 secs on MARINE compared to Nanoflann’s 3.91 secs. During insertions, Nanoflann remains competitive, outperforming our KD-tree in MARINE but losing in the other datasets. As mentioned in the 2D case, Nanoflann’s deletions remain fast due its tombstoning strategy. Figure 15 shows that the query latency gap remains in 3D space. Our KD-tree dominates Nanoflann across both range and 𝑘NN searches. On range queries, Nanoflann is orders of magnitude slower than Indexicon’s KD-tree. For 𝑘NN queries, Nanoflann still underperforms, thus, showing that our KD-tree scales gracefully to 3D environments and the severe compounding effects of dynamic Nanoflann’s architecture.

Conclusions

We introduced Indexicon, a portable, open-source spatial indexing library engineered to bridge the gap between software simplicity and high-performance code for main-memory applications. By consolidating three foundational spatial structures, and their variants, into self-contained implementations, Indexicon systematically eliminates the fragmented APIs, heavy dependencies, and code complexity that plague the current open-source spatial indexing ecosystem. Our extensive empirical evaluation across six real-world geographic datasets demonstrates that Indexicon consistently matches or outperforms competitive open-source indexing libraries and implementations proving that structural flexibility does not require sacrificing execution efficiency.

Future work

Although in its current state our library is fully deployable and addresses all three challenges outlined in the introduction, we are constantly evolving it along the following priority axes: • Improved support for updates. Our KD-tree implementation currently does not support re-balancing under dynamic updates. We plan to investigate mechanisms that detect and repair imbalances caused by insertions or deletions. We also plan to extend the Oct-tree with additional 3D splitting strategies, including median-based variants analogous to those currently supported by our 2D Quadtree implementations. • Additional spatial indices. We plan to expand Indexicon to include additional spatial indices (e.g., a 3D MX-CIF, KDBTree [55], Waffle [41]). Furthermore, recent studies [38, 39, 65, 66] show that grid-based structures can outperform treebased ones in main memory. In the near future, we plan to implement uniform and adaptive 2D and 3D grids that support both point and MBB data. • Support for other query types. In addition to range and nearest neighbor queries that we already support, we plan to include support for spatial (intersection and distance) joins in the implementations of the spatial indices.

• Multi-threaded search and updates. We plan to include locking mechanisms to the spatial indices that enable highthroughput search and updates, while ensuring data consistency. For this, we plan to borrow ideas from our recent work in data-parallel and multi-threaded indexing [67]. Besides our own efforts to improve and expand Indexicon, we hope to engage the community in contributing to this project, offering improvements and extensions beyond the ones discussed above, constantly advancing Indexicon’s open-source capabilities.

References [1] Daichi Amagata, Panagiotis Simatis, Panagiotis Bouros, and Nikos Mamoulis. 2026. FIRAS: A Framework for Interval Range Search and Sampling. Proceedings of the ACM on Management of Data 4, 3 (SIGMOD (2026), 1–26. doi:10.1145/ 3802062 [2] Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. 1999. OPTICS: Ordering Points To Identify the Clustering Structure. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA. ACM Press, 49–60. doi:10.1145/304182. 304187 [3] Tinko Sebastian Bartels, Vissarion Fisikopoulos, Barend Gehrels, Menelaos Karavelas, Bruno Lalande, Mateusz Łoskot, and Adam Wulkiewicz. 2026. Boost.Geometry: A Generic C++ Geometry Library. Journal of Open Source Software 11, 121 (2026), 10328. doi:10.21105/joss.10328 [4] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, USA, May 23-25, 1990. ACM Press, 322–331. doi:10.1145/93597.98741 [5] Jon Louis Bentley. 1975. Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18, 9 (1975), 509–517. doi:10.1145/361002.361007 [6] Thomas Bernecker, Tobias Emrich, Hans-Peter Kriegel, Nikos Mamoulis, Matthias Renz, and Andreas Züfle. 2011. A novel probabilistic pruning approach to speed up similarity queries in uncertain databases. In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany. IEEE Computer Society, 339–350. doi:10.1109/ICDE.2011.5767908 [7] Jose Luis Blanco and Pranjal Kumar Rai. 2014. nanoflann: a C++ header-only fork of FLANN, a library for Nearest Neighbor (NN) with KD-trees. https: //github.com/jlblancoc/nanoflann. [8] Thomas Brinkhoff, Hans-Peter Kriegel, and Ralf Schneider. 1993. Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. In Proceedings of the Ninth International Conference on Data Engineering, April 19-23, 1993, Vienna, Austria. IEEE Computer Society, 40–49. doi:10.1109/ICDE.1993.344079 [9] Marine Cadastre. 2026. Vessel Traffic Data. https://hub.marinecadastre.gov/ pages/vesseltraffic [10] US Census. 2026. TIGER/Line Shapefiles. https://www.census.gov/geographies/ mapping-files/time-series/geo/tiger-line-file.html [11] Lu Chen, Yunjun Gao, Baihua Zheng, Christian S. Jensen, Hanyu Yang, and Keyu Yang. 2017. Pivot-based Metric Indexing. Proc. VLDB Endow. 10, 10 (2017), 1058–1069. doi:10.14778/3115404.3115411 [12] Youguang Chen, William Ruys, and George Biros. 2025. KNN-DBSCAN: a DBSCAN in high dimensions. ACM Trans. Parallel Comput. 12, 1 (2025), 3:1–3:27. doi:10.1145/3701624 [13] George Christodoulou, Panagiotis Bouros, and Nikos Mamoulis. 2022. HINT: A Hierarchical Index for Intervals in Main Memory. In SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022. ACM, 1257–1270. doi:10.1145/3514221.3517873 [14] George Christodoulou, Panagiotis Bouros, and Nikos Mamoulis. 2024. LIT: Lightning-fast In-memory Temporal Indexing. Proc. ACM Manag. Data 2, 1 (2024), 20:1–20:27. doi:10.1145/3639275 [15] NYC Taxi & Limousine Commission. 2026. TLC Trip Record Data. https://www. nyc.gov/site/tlc/about/tlc-trip-record-data.page [16] Evangelos Dellis and Bernhard Seeger. 2007. Efficient Computation of Reverse Skyline Queries. In Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007. ACM, 291–302. http://www.vldb.org/conf/2007/papers/research/p291-dellis.pdf [17] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Michael Wimmer, and Xiaowei Xu. 1998. Incremental Clustering for Mining in a Data Warehousing Environment. In VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann, 323–333. http://www.vldb.org/conf/1998/p323.pdf

Simatis et al.

[18] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A DensityBased Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Oregon, USA. AAAI Press, 226–231. http: //www.aaai.org/Library/KDD/1996/kdd96-037.php [19] Raphael A. Finkel and Jon Louis Bentley. 1974. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica 4 (1974), 1–9. doi:10.1007/ BF00288933 [20] Jerome H. Friedman, Jon Louis Bentley, and Raphael A. Finkel. 1977. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Softw. 3, 3 (1977), 209–226. doi:10.1145/355744.355745 [21] Volker Gaede and Oliver Günther. 1998. Multidimensional Access Methods. ACM Comput. Surv. 30, 2 (1998), 170–231. doi:10.1145/280277.280279 [22] Yván J. García, Mario Alberto López, and Scott T. Leutenegger. 1998. A Greedy Algorithm for Bulk Loading R-Trees. In ACM-GIS ’98, Proceedings of the 6th international symposium on Advances in Geographic Information Systems, November 6-7, 1998, Washington, DC, USA. ACM, 163–164. doi:10.1145/288692.288723 [23] GEOS contributors. 2025. GEOS computational geometry library. Open Source Geospatial Foundation. doi:10.5281/zenodo.11396894 [24] Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD’84, Proceedings of Annual Meeting, Boston, Massachusetts, USA, June 18-21, 1984. ACM Press, 47–57. doi:10.1145/602259.602266 [25] Marios Hadjieleftheriou and Howard Butler. 2024. libspatialindex. https:// libspatialindex.org. Version 2.0.0. [26] Stratos Idreos, Martin L. Kersten, and Stefan Manegold. 2007. Database Cracking. In Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7-10, 2007, Online Proceedings. www.cidrdb.org, 68–78. http://cidrdb.org/cidr2007/papers/cidr07p07.pdf [27] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. 2002. An Efficient k-Means Clustering Algorithm: Analysis and Implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24, 7 (2002), 881–892. doi:10.1109/TPAMI.2002.1017616 [28] Norio Katayama and Shin’ichi Satoh. 1997. The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. In SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA. ACM Press, 369–380. doi:10.1145/253260.253347 [29] Per-Åke Larson and Justin J. Levandoski. 2016. Modern Main-Memory Database Systems. Proc. VLDB Endow. 9, 13 (2016), 1609–1610. doi:10.14778/3007263. 3007321 [30] Scott T. Leutenegger, Jeffrey Edgington, and Mario Alberto López. 1997. STR: A Simple and Efficient Algorithm for R-Tree Packing. In Proceedings of the Thirteenth International Conference on Data Engineering, April 7-11, 1997, Birmingham, UK. IEEE Computer Society, 497–506. doi:10.1109/ICDE.1997.582015 [31] Mingxin Li, Hancheng Wang, Haipeng Dai, Meng Li, Chengliang Chai, Rong Gu, Feng Chen, Zhiyuan Chen, Shuaituan Li, Qizhi Liu, and Guihai Chen. 2024. A Survey of Multi-Dimensional Indexes: Past and Future Trends. IEEE Trans. Knowl. Data Eng. 36, 8 (2024), 3635–3655. doi:10.1109/TKDE.2024.3364183 [32] Xiang Lian and Lei Chen. 2008. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008. ACM, 213–226. doi:10.1145/1376616.1376641 [33] Qiyu Liu, Maocheng Li, Yuxiang Zeng, Yanyan Shen, and Lei Chen. 2025. How good are multi-dimensional learned indexes? An experimental survey. VLDB J. 34, 2 (2025), 17. doi:10.1007/S00778-024-00893-6 [34] Xingjie Liu, De-Nian Yang, Mao Ye, and Wang-Chien Lee. 2013. U-Skyline: A New Skyline Query for Uncertain Databases. IEEE Trans. Knowl. Data Eng. 25, 4 (2013), 945–960. doi:10.1109/TKDE.2012.33 [35] Mateusz Loskot and Adam Wulkiewicz. 2019. {https}://github.com/mloskot/ spatial_index_benchmark [36] Arlino Magalhães, Angelo Brayner, and José Maria Monteiro. 2023. Main Memory Database Recovery Strategies. In Companion of the 2023 International Conference on Management of Data, SIGMOD/PODS 2023, Seattle, WA, USA, June 18-23, 2023. ACM, 31–35. doi:10.1145/3555041.3589402 [37] Nikos Mamoulis. 2011. Spatial Data Management. Morgan & Claypool Publishers. doi:10.2200/S00394ED1V01Y201111DTM021 [38] Achilleas Michalopoulos, Dimitrios Tsitsigkos, Panagiotis Bouros, Nikos Mamoulis, and Manolis Terrovitis. 2023. Efficient Nearest Neighbor Queries on Non-point Data. In Proceedings of the 31st ACM International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2023, Hamburg, Germany, November 13-16, 2023. ACM, 33:1–33:4. doi:10.1145/3589132.3625609 [39] Achilleas Michalopoulos, Dimitrios Tsitsigkos, Panagiotis Bouros, Nikos Mamoulis, and Manolis Terrovitis. 2025. Efficient Distance Queries on Nonpoint Data. ACM Trans. Spatial Algorithms Syst. 11, 1 (2025), 1:1–1:37. doi:10. 1145/3698194 [40] Michael D. Morse, Jignesh M. Patel, and William I. Grosky. 2006. Efficient Continuous Skyline Computation. In Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA. IEEE Computer Society, 108. doi:10.1109/ICDE.2006.56

[41] Moin Hussain Moti, Panagiotis Simatis, and Dimitris Papadias. 2022. Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing. Proc. VLDB Endow. 16, 4 (2022), 670–683. doi:10.14778/3574245.3574253 [42] Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis. 2006. Continuous Nearest Neighbor Monitoring in Road Networks. In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, 2006. ACM, 43–54. http://dl.acm.org/citation.cfm?id=1164133 [43] Marius Muja and David G. Lowe. 2009. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In International Conference on Computer Vision Theory and Application VISSAPP’09). INSTICC Press, 331–340. [44] Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data. IEEE Trans. Pattern Anal. Mach. Intell. 36, 11 (2014), 2227–2240. doi:10.1109/TPAMI.2014.2321376 [45] Kun Seok Oh, Yaokai Feng, Kunihiko Kaneko, Akifumi Makinouchi, and SangHyun Bae. 2001. SOM-Based R*-tree for Similarity Retrieval. In Database Systems for Advanced Applications, Proceedings of the 7th International Conference on Database Systems for Advanced Applications (DASFAA 2001), 18-20 April 2001 Hong Kong, China. IEEE Computer Society, 182–189. doi:10.1109/DASFAA.2001. 916377 [46] OpenStreetMap contributors. 2017. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org. [47] Mark H. Overmars and Jan van Leeuwen. 1982. Dynamic Multi-Dimensional Data Structures Based on Quad- and K - D Trees. Acta Informatica 17 (1982), 267–285. doi:10.1007/BF00264354 [48] Varun Pandey, Andreas Kipf, Thomas Neumann, and Alfons Kemper. 2018. How Good Are Modern Spatial Analytics Systems? Proc. VLDB Endow. 11, 11 (2018), 1661–1673. doi:10.14778/3236187.3236213 [49] Varun Pandey, Alexander van Renen, Andreas Kipf, and Alfons Kemper. 2021. How Good Are Modern Spatial Libraries? Data Sci. Eng. 6, 2 (2021), 192–208. doi:10.1007/S41019-020-00147-9 [50] Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. 2003. An Optimal and Progressive Algorithm for Skyline Queries. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003. ACM, 467–478. doi:10.1145/872757.872814 [51] Sungwoo Park, Taekyung Kim, Jonghyun Park, Jinha Kim, and Hyeonseung Im. 2009. Parallel Skyline Computation on Multicore Architectures. In Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China. IEEE Computer Society, 760–771. doi:10. 1109/ICDE.2009.42 [52] Austin Parker, Guillaume Infantes, John Grant, and V. S. Subrahmanian. 2009. SPOT Databases: Efficient Consistency Checking and Optimistic Selection in Probabilistic Spatial Databases. IEEE Trans. Knowl. Data Eng. 21, 1 (2009), 92–107. doi:10.1109/TKDE.2008.93 [53] Dan Pelleg and Andrew W. Moore. 1999. Accelerating Exact k-means Algorithms with Geometric Reasoning. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 15-18, 1999. ACM, 277–281. doi:10.1145/312129.312248 [54] G.P. Robinson, H.D. Tagare, J.S. Duncan, and C.C. Jaffe. 1996. Medical image collection indexing: Shape-based retrieval using KD-trees. Computerized Medical Imaging and Graphics 20, 4 (1996), 209–217. doi:10.1016/S0895-6111(96)00014-6 Medical Image Databases. [55] John T. Robinson. 1981. The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. In Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, USA, April 29 May 1, 1981. ACM Press, 10–18. doi:10.1145/582318.582321 [56] Radu Bogdan Rusu and Steve Cousins. 2011. 3D is here: Point Cloud Library (PCL). In IEEE International Conference on Robotics and Automation, ICRA 2011, Shanghai, China, 9-13 May 2011. IEEE. doi:10.1109/ICRA.2011.5980567 [57] Hanan Samet. 1984. The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16, 2 (1984), 187–260. doi:10.1145/356924.356930 [58] Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press. [59] Chanop Silpa-Anan and Richard I. Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2008), 24-26 June 2008, Anchorage, Alaska, USA. IEEE Computer Society. doi:10.1109/CVPR.2008.4587638 [60] Panagiotis Simatis, George Christodoulou, Panagiotis Bouros, and Nikos Mamoulis. 2026. Scalable lighting-fast temporal indexing. VLDB J. 35, 3 (2026), 17. doi:10.1007/S00778-026-00968-6 [61] Huaiguang Song, Zhongbo Wu, Binglei Guo, Zhao Wu, and Min Wang. 2025. An efficient approach towards index structures for skyline queries. J. King Saud Univ. Comput. Inf. Sci. 37, 3 (2025). doi:10.1007/S44443-025-00183-3 [62] Weikai Tan, Nannan Qin, Lingfei Ma, Ying Li, Jing Du, Guorong Cai, Ke Yang, and Jonathan Li. 2020. Toronto-3D: A Large-scale Mobile LiDAR Dataset for Semantic Segmentation of Urban Roadways. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR Workshops 2020, Seattle, WA, USA, June 14-19, 2020. Computer Vision Foundation / IEEE, 797–806. doi:10.1109/ CVPRW50498.2020.00109

Indexicon: A Spatial Indexing Library

[63] Yufei Tao, Xiaokui Xiao, and Reynold Cheng. 2007. Range search on multidimensional uncertain data. ACM Trans. Database Syst. 32, 3 (2007), 15. doi:10.1145/1272743.1272745 [64] The CGAL Project [n. d.]. CGAL, Computational Geometry Algorithms Library. The CGAL Project. https://www.cgal.org [65] Dimitrios Tsitsigkos, Panagiotis Bouros, Konstantinos Lampropoulos, Nikos Mamoulis, and Manolis Terrovitis. 2024. Two-Layer Space-Oriented Partitioning for Non-Point Data. IEEE Trans. Knowl. Data Eng. 36, 3 (2024), 1341–1355. doi:10.1109/TKDE.2023.3297975 [66] Dimitrios Tsitsigkos, Konstantinos Lampropoulos, Panagiotis Bouros, Nikos Mamoulis, and Manolis Terrovitis. 2021. A Two-layer Partitioning for Non-point Spatial Data. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021. IEEE, 1787–1798. doi:10.1109/ICDE51399. 2021.00157 [67] Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, and Manolis Terrovitis. 2026. BS-tree: A gapped data-parallel B-tree. In IEEE International Conference on Data Engineering (ICDE 2026), 5-8 May 2026, Montreal, Canada. IEEE Computer Society. doi:10.1109/ICDE65706.2026.00040 [68] Pierre Vigier. 2019. A C++17 Quadtree. https://github.com/pvigier/Quadtree. Accessed: 2026-05-27. [69] Akrivi Vlachou, Christos Doulkeridis, Kjetil Nørvåg, and Yannis Kotidis. 2013. Branch-and-bound algorithm for reverse top-k queries. In Proceedings of the ACM

SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013. ACM, 481–492. doi:10.1145/2463676.2465278 [70] Benjamin Wilson, William Qi, Tanmay Agarwal, John Lambert, Jagjeet Singh, Siddhesh Khandelwal, Bowen Pan, Ratnesh Kumar, Andrew Hartnett, Jhony Kaesemodel Pontes, Deva Ramanan, Peter Carr, and James Hays. 2021. Argoverse 2: Next Generation Datasets for Self-Driving Perception and Forecasting. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual. https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/ 4734ba6f3de83d861c3176a6273cac6d-Abstract-round2.html [71] Guoqing Wu, Liqiang Cao, Hongyun Tian, and Wei Wang. 2022. HY-DBSCAN: A hybrid parallel DBSCAN clustering algorithm scalable on distributed-memory computers. J. Parallel Distributed Comput. 168 (2022), 57–69. doi:10.1016/J.JPDC. 2022.06.005 [72] Pengcheng Wu, Steven C. H. Hoi, Duc Dung Nguyen, and Ying He. 2011. Randomly Projected KD-Trees with Distance Metric Learning for Image Retrieval. In Advances in Multimedia Modeling - 17th International Multimedia Modeling Conference, MMM 2011, Taipei, Taiwan, January 5-7, 2011, Proceedings, Part II (Lecture Notes in Computer Science). Springer, 371–382. doi:10.1007/978-3-642-17829-0_35 [73] Hyountaek Yong, Jongwuk Lee, Jinha Kim, and Seung-won Hwang. 2014. Skyline ranking for uncertain databases. Inf. Sci. 273 (2014), 247–262. doi:10.1016/J.INS. 2014.03.044

Indexicon: A Spatial Indexing Library

Related documents