geokdtree

GeoKDTree

PyPI version License: MIT PyPI Downloads

Ultra-fast nearest-neighbor lookup for latitude/longitude data

GeoKDTree is a lightweight, high-performance spatial indexing library for Python designed to find the nearest geographic coordinate from massive datasets in nanoseconds.

It wraps a highly optimized KD-Tree with a geographic interface, allowing you to work directly with (latitude, longitude) pairs. No projections, no external dependencies, and no heavy GIS stacks.

geokdtree

Documentation

Installation

Standard Installation (with C++ acceleration)

pip install geokdtree

Pure Python Installation (Skip Binary Builds)

If you want to install geokdtree in pure Python mode without compiling or using binary extensions (or in environments without a C++ compiler):

  • Linux / macOS / WSL2:

    GEOKDTREE_NO_BUILD=1 pip install --no-binary geokdtree geokdtree

    Or with uv:

    GEOKDTREE_NO_BUILD=1 uv pip install --no-binary geokdtree geokdtree

  • Windows (PowerShell):

    $env:GEOKDTREE_NO_BUILD="1"
pip install --no-binary geokdtree geokdtree

  • Windows (CMD):

    set GEOKDTREE_NO_BUILD=1
pip install --no-binary geokdtree geokdtree

Automatic Fallback

When building from source, if a C++ compiler is not available or compilation fails, geokdtree will automatically fall back to the pure Python implementation.

Getting Started

from geokdtree import GeoKDTree

example_points = [
    (34.0522, -118.2437),  # Los Angeles
    (40.7128, -74.0060),  # New York
    (37.7749, -122.4194),  # San Francisco
    (51.5074, -0.1278),  # London
    (48.8566, 2.3522),  # Paris
]

geo_kd_tree = GeoKDTree(points=example_points)

test_point = (47.6062, -122.3321)  # Seattle
# Find the index of the closest point in the original dataset
closest_idx = geo_kd_tree.closest_idx(test_point)  # => 2
# Find the closest point itself
closest_point = geo_kd_tree.closest_point(test_point)  # => (37.7749, -122.4194)

# Find closest points in each quadrant (ne, nw, se, sw)
quadrants = geo_kd_tree.closest_point_per_quadrant(test_point)
# => {'ne': (51.5074, -0.1278), 'nw': None, 'se': (40.7128, -74.006), 'sw': (37.7749, -122.4194)}

Why Use GeoKDTree?

GeoKDTree is designed to solve one focused problem extremely well:

Fast nearest-neighbor lookup for latitude/longitude data at scale.

It is worth noting that the closest point found may not be the true closest point, but should be very close for most practical applications. See KD-Tree limitations for more details.

Extremely Fast Lookups

Once constructed, nearest-neighbor queries consistently complete in hundreds of nanoseconds to single-digit microseconds, even with 1,000,000 coordinates.

Typical benchmark results (see benchmark.md for full benchmarks):

Number of Points ($N$) C++ Build Time Python Build Time C++ Query Time Python Query Time Query Speedup
1,000 ~1.1 ms ~1.6 ms ~0.65 µs ~12.5 µs ~19x
10,000 ~15 ms ~21 ms ~0.85 µs ~16.1 µs ~19x
100,000 ~225 ms ~350 ms ~1.8 µs ~24.0 µs ~13x
1,000,000 ~3.8 s ~6.3 s ~3.2 µs ~31.5 µs ~10x

This makes GeoKDTree well-suited for:

  • Real-time proximity queries
  • Matching incoming coordinates against large reference datasets
  • High-throughput geospatial APIs
  • Pre-filtering before more expensive geospatial calculations

Exact timings depend on hardware, Python version, and data distribution. These values reflect typical results from utils/benchmark.py.

Built for Geographic Coordinates

GeoKDTree works directly with (latitude, longitude) pairs.

You do not need to:

  • Project coordinates into planar space
  • Use heavyweight GIS libraries
  • Maintain custom spatial indexing code

Just pass geographic coordinates and query.

Simple API, Zero Runtime Dependencies

GeoKDTree intentionally keeps the API small and focused.

  • Build once from a list of coordinates
  • Query nearest neighbors with a single method call
  • Retrieve indices or points directly from your original dataset
  • Zero external runtime dependencies, with optional C++ acceleration via nanobind and automatic pure Python fallback.

Deterministic and Predictable Performance

  • Tree construction scales at approximately $O(N \log N)$
  • Query performance scales at approximately $O(\log N)$
  • No probabilistic approximations
  • No background indexing or caching

This predictability is valuable for production systems where latency and reproducibility matter.

Supported Features

See: https://connor-makowski.github.io/geokdtree/geokdtree.html

Contributing

Issues, feature requests, and pull requests are welcome. Please open an issue to discuss changes or enhancements.

Development

Setup & Testing

  1. Clone the repository and install development dependencies:

    uv sync --extra dev --reinstall-package geokdtree

  2. Run the test suite:

    uv run pytest

  3. Run full test matrix across Python versions (3.11–3.14 & PyPy3.11):

    uv run nox

  4. Run performance benchmarks:

    uv run python utils/benchmark.py

  5. Prettify and format code:

    uv run python utils/prettify.py

  1r"""
  2# GeoKDTree
  3[![PyPI version](https://badge.fury.io/py/geokdtree.svg)](https://badge.fury.io/py/geokdtree)
  4[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
  5[![PyPI Downloads](https://pepy.tech/badge/geokdtree)](https://pypi.org/project/geokdtree/)
  6<!-- [![PyPI Downloads](https://img.shields.io/pypi/dm/geokdtree.svg?label=PyPI%20downloads)](https://pypi.org/project/geokdtree/) -->
  7
  8## Ultra-fast nearest-neighbor lookup for latitude/longitude data
  9
 10**GeoKDTree** is a lightweight, high-performance spatial indexing library for Python designed to find the *nearest geographic coordinate* from massive datasets in nanoseconds.
 11
 12It wraps a highly optimized KD-Tree with a geographic interface, allowing you to work directly with `(latitude, longitude)` pairs. No projections, no external dependencies, and no heavy GIS stacks.
 13
 14![geokdtree](https://raw.githubusercontent.com/connor-makowski/geokdtree/main/static/geokdtree.png)
 15
 16### Documentation
 17
 18- Docs: https://connor-makowski.github.io/geokdtree/geokdtree.html
 19- Git Repo: https://github.com/connor-makowski/geokdtree
 20
 21## Installation
 22
 23### Standard Installation (with C++ acceleration)
 24
 25```bash
 26pip install geokdtree
 27```
 28
 29### Pure Python Installation (Skip Binary Builds)
 30
 31If you want to install `geokdtree` in pure Python mode without compiling or using binary extensions (or in environments without a C++ compiler):
 32
 33- **Linux / macOS / WSL2**:
 34  ```bash
 35  GEOKDTREE_NO_BUILD=1 pip install --no-binary geokdtree geokdtree
 36  ```
 37  Or with `uv`:
 38  ```bash
 39  GEOKDTREE_NO_BUILD=1 uv pip install --no-binary geokdtree geokdtree
 40  ```
 41
 42- **Windows (PowerShell)**:
 43  ```powershell
 44  $env:GEOKDTREE_NO_BUILD="1"
 45  pip install --no-binary geokdtree geokdtree
 46  ```
 47
 48- **Windows (CMD)**:
 49  ```cmd
 50  set GEOKDTREE_NO_BUILD=1
 51  pip install --no-binary geokdtree geokdtree
 52  ```
 53
 54#### Automatic Fallback
 55When building from source, if a C++ compiler is not available or compilation fails, `geokdtree` will automatically fall back to the pure Python implementation.
 56
 57## Getting Started
 58
 59```python
 60from geokdtree import GeoKDTree
 61
 62example_points = [
 63    (34.0522, -118.2437),  # Los Angeles
 64    (40.7128, -74.0060),  # New York
 65    (37.7749, -122.4194),  # San Francisco
 66    (51.5074, -0.1278),  # London
 67    (48.8566, 2.3522),  # Paris
 68]
 69
 70geo_kd_tree = GeoKDTree(points=example_points)
 71
 72test_point = (47.6062, -122.3321)  # Seattle
 73# Find the index of the closest point in the original dataset
 74closest_idx = geo_kd_tree.closest_idx(test_point)  # => 2
 75# Find the closest point itself
 76closest_point = geo_kd_tree.closest_point(test_point)  # => (37.7749, -122.4194)
 77
 78# Find closest points in each quadrant (ne, nw, se, sw)
 79quadrants = geo_kd_tree.closest_point_per_quadrant(test_point)
 80# => {'ne': (51.5074, -0.1278), 'nw': None, 'se': (40.7128, -74.006), 'sw': (37.7749, -122.4194)}
 81```
 82
 83## Why Use GeoKDTree?
 84
 85GeoKDTree is designed to solve one focused problem extremely well:
 86
 87**Fast nearest-neighbor lookup for latitude/longitude data at scale.**
 88
 89It is worth noting that the closest point found may not be the true closest point, but should be very close for most practical applications. See KD-Tree limitations for more details.
 90
 91### Extremely Fast Lookups
 92
 93Once constructed, nearest-neighbor queries consistently complete in **hundreds of nanoseconds to single-digit microseconds**, even with 1,000,000 coordinates.
 94
 95Typical benchmark results (see [benchmark.md](benchmark.md) for full benchmarks):
 96
 97| Number of Points ($N$) | C++ Build Time | Python Build Time | C++ Query Time | Python Query Time | Query Speedup |
 98| ---------------------: | -------------: | ----------------: | -------------: | ----------------: | ------------: |
 99|                  1,000 |        ~1.1 ms |           ~1.6 ms |       ~0.65 µs |          ~12.5 µs |          ~19x |
100|                 10,000 |         ~15 ms |            ~21 ms |       ~0.85 µs |          ~16.1 µs |          ~19x |
101|                100,000 |        ~225 ms |           ~350 ms |        ~1.8 µs |          ~24.0 µs |          ~13x |
102|              1,000,000 |         ~3.8 s |            ~6.3 s |        ~3.2 µs |          ~31.5 µs |          ~10x |
103
104This makes GeoKDTree well-suited for:
105
106* Real-time proximity queries
107* Matching incoming coordinates against large reference datasets
108* High-throughput geospatial APIs
109* Pre-filtering before more expensive geospatial calculations
110
111> Exact timings depend on hardware, Python version, and data distribution. These values reflect typical results from `utils/benchmark.py`.
112
113### Built for Geographic Coordinates
114
115GeoKDTree works directly with `(latitude, longitude)` pairs.
116
117You do **not** need to:
118
119* Project coordinates into planar space
120* Use heavyweight GIS libraries
121* Maintain custom spatial indexing code
122
123Just pass geographic coordinates and query.
124
125### Simple API, Zero Runtime Dependencies
126
127GeoKDTree intentionally keeps the API small and focused.
128
129* Build once from a list of coordinates
130* Query nearest neighbors with a single method call
131* Retrieve indices or points directly from your original dataset
132* Zero external runtime dependencies, with optional C++ acceleration via `nanobind` and automatic pure Python fallback.
133
134### Deterministic and Predictable Performance
135
136* Tree construction scales at approximately $O(N \log N)$
137* Query performance scales at approximately $O(\log N)$
138* No probabilistic approximations
139* No background indexing or caching
140
141This predictability is valuable for production systems where latency and reproducibility matter.
142
143## Supported Features
144
145See: https://connor-makowski.github.io/geokdtree/geokdtree.html
146
147## Contributing
148
149Issues, feature requests, and pull requests are welcome.
150Please open an issue to discuss changes or enhancements.
151
152## Development
153
154### Setup & Testing
155
1561. Clone the repository and install development dependencies:
157   ```bash
158   uv sync --extra dev --reinstall-package geokdtree
159   ```
160
1612. Run the test suite:
162   ```bash
163   uv run pytest
164   ```
165
1663. Run full test matrix across Python versions (3.11–3.14 & PyPy3.11):
167   ```bash
168   uv run nox
169   ```
170
1714. Run performance benchmarks:
172   ```bash
173   uv run python utils/benchmark.py
174   ```
175
1765. Prettify and format code:
177   ```bash
178   uv run python utils/prettify.py
179   ```
180
181"""
182
183import os
184
185if os.environ.get("GEOKDTREE_REQUIRE_PYTHON") == "1":
186    from geokdtree.geokdtree import GeoKDTree
187    from geokdtree.kdtree import KDTree
188else:
189    try:
190        from geokdtree.cpp import GeoKDTree, KDTree
191    except ImportError:
192        from geokdtree.geokdtree import GeoKDTree
193        from geokdtree.kdtree import KDTree