View all files | ||||
I often must modify or benchmark a spatial index. Unfortunately, most implementations are complex or lack features. That's why I made Indexicon, a drop-in spatial index library with top-tier performance.
To compile and test all indexes:
| R-tree | rtree_point.hpp, rtree_mbr.hpp | Any | Point / MBB | An R-tree supporting decoupled internal and leaf node capacities. It features top-down bulk loading and R* insertions. Deletions dissolve sparse nodes and reinsert orphans. rtree_point.hpp and rtree_mbr.hpp are nearly identical implementations for point and MBB data, respectively. |
| Quad-tree | quadtree.hpp | 2D | Point | A Quad-tree supporting three splitting strategies: Point-Region (PR) (geometric midpoints), Pseudo-median (independent axis medians), and Longest-axis (median of the widest span). It features bulk-loading, out-of-bounds insertions, and leaf overflows to handle duplicate points. |
| MX-CIF Quad-tree | mxcif_quadtree.hpp | 2D | MBB | An MX-CIF Quad-tree utilizing the PR splitting strategy. It handles spatial extents by storing boundary-straddling MBBs in internal nodes, while non-straddling MBBs are stored in bucket leaves. |
| Oct-tree | octtree.hpp | 3D | Point | A 3D extension of the PR Quad-tree that divides space into equal octants at the midpoint of each axis. |
| KD-tree | kdtree.hpp | Any | Point | A KD-tree with binary space partitioning and bucket leaves. The splitting dimension is chosen via Adaptive (widest data spread), Round-robin (depth cycling), or Longest-axis (widest bounding box) strategies. Bulk-loading recurisevely halves data at the median coordinate. Insertions split leaves, while deletions merge underflowing sibling leaves. |
Indexicon's R-tree against Boost's R-tree on insertion and range query times for various node capacities.
Note: For a comprehensive performance evaluation including all indexes, refer to our accompanying paper.
Datasets and query files can be downloaded here. You can generate your own queries using the query generator provided.
| MARINE | 25.0M | Point | 716.2 MB | 3D | 0.01% | US coastal vessel tracking data |
| MIAMI | 3.5M | MBB | 312.2 MB | 3D | 0.02% | Urban traffic-object MBBs in Miami |
| OSM | 103.5M | Point | 2.0 GB | 2D | 0.03% | Geolocations in Central America |
| TAXIS | 112.8M | Point | 2.2 GB | 2D | 14.55% | NYC Taxi pickup geolocations |
| TIGER | 17.9M | MBB | 715.2 MB | 2D | 5.60% | Lower 48 street MBBs |
| TORONTO | 21.6M | Point | 679.5 MB | 3D | 6.94% | Toronto urban LiDAR point cloud |
Requirements: a C++17-compatible compiler.
Compile and run a single test:
The tests are the best usage examples. Each one shows the full flow for an index: load data, bulk load, insert, delete, range query, kNN query, and statistics.
Contributions are welcome. Before submitting a pull request, please ensure the following:
Hopefully, Indexicon will grow into a grimoire of indexes, expanded by those brave enough to peer into the geometry of the unknown.
This project is licensed under the MIT License. See LICENSE for details.
If you use Indexicon in a project, paper, benchmark, or product, please cite:
The accompanying paper is available on arXiv: https://arxiv.org/abs/2606.04676