RDT Spatial Index

RDT Spatial Index is a research-grade repository for adaptive spatial indexing. It includes readable reference implementations, practical fast paths, optional compiled query backends, baseline comparisons, and reproducibility artifacts.

The project is organized for external review: tests, benchmarks, limitations, and publication-oriented outputs are part of the repository.

Start Here

• IMPLEMENTATIONS.md: recommended class path and backend matrix.
• TESTING.md: correctness and consistency test entry points.
• BENCHMARKS.md: quick and publication benchmark commands.
• REPRODUCIBILITY.md: end-to-end reproduction flow.
• RESULTS_SUMMARY.md: concise evidence summary.
• LIMITATIONS.md: known weaknesses and caveats.
• RELEASE_NOTES.md: release highlights and migration notes.
• DOCUMENTATION_INDEX.md: full navigation index.

Recommended Implementation Path

1. Use RDTFastIndex as the default practical implementation.
2. Use RDTIndex as the reference correctness baseline.
3. Add RDTCIndex, RDTCythonIndex, or RDTNumbaIndex only when compiled acceleration is needed and your environment supports it.

Install

pip install -e .

Optional extras:

pip install -e ".[bench]"      # benchmark dependencies
pip install -e ".[accel]"      # optional acceleration dependencies
pip install -e ".[bench_full]" # includes rtree (needs libspatialindex on many systems)

Node.js Package

A publishable npm package is included at packages/rdt-spatial-index.

cd packages/rdt-spatial-index
npm install
npm test

Target package name:

@sreid90/rdt-spatial-index

Quick Start

import numpy as np
from rdt_spatial_index import RDTFastIndex

points = np.random.default_rng(1).uniform(0, 1000, size=(20_000, 2))
queries = np.random.default_rng(2).uniform(0, 1000, size=(256, 2))

idx = RDTFastIndex(alpha=1.5, max_leaf=96)
idx.build(points)
counts = idx.query(queries, radius=30.0)
print(counts[:5])

Validate Your Environment

python tests/run_tests.py
python tests/ci/verify_core_imports.py

Optional compiled verification:

python rdt_spatial_index/c_ext/setup.py build_ext --inplace
python rdt_spatial_index/setup_cython.py build_ext --inplace
python tests/ci/verify_compiled_wrappers.py

Benchmark and Reproduce

python benchmarks/compare_indexes.py --n 50000
python benchmarks/pub_benchmark.py --fast
python benchmarks/generate_figures.py

Or run:

./run_publication_suite.sh --fast

Results Snapshot

• Correctness: RDT variants are exact on the included brute-force checks.
• Performance: workload-dependent, not universally dominant.
• Compiled backends: can materially improve query time and should be reported separately from pure-Python comparisons.
• Reproducibility: raw outputs, figures, and tables are versioned in-repo.

See RESULTS_SUMMARY.md and publication/RESULTS_SUMMARY.md.

Limitations Up Front

• No universal superiority claim over grid/KD-tree/R-tree families.
• Performance depends on workload, parameters, and backend.
• Optional dependencies (scipy, rtree, compiler toolchains) affect which comparisons are available.
• Experimental modules under experiments/ are exploratory, not stable API.

See LIMITATIONS.md.

Repository Layout

• Source package: rdt_spatial_index/
• Benchmarks: benchmarks/
• Tests: tests/
• Reproducibility package: publication/
• Quick benchmark outputs: results/
• Experiments: experiments/
• Legacy archive: legacy/

Citation

If this repository contributes to your work, cite via CITATION.cff.

Contributing

See CONTRIBUTING.md.

License

MIT. See LICENSE.