jlblancoc/nanoflann

nanoflann: a C++11 header-only library for Nearest Neighbor (NN) search with KD-trees

What it solves

nanoflann is a high-performance C++ library designed for building KD-trees to perform fast nearest-neighbor searches. It addresses the performance and memory overhead found in earlier libraries (like FLANN) by eliminating virtual method calls and avoiding unnecessary data duplication.

How it works

The library uses a header-only implementation based on the Curiously Recurring Template Pattern (CRTP) and inlined methods to maximize execution speed. Instead of copying datasets into internal matrices, it uses an adaptor interface that allows the KD-tree to access data directly from the user's own data structures. It supports both static indices and dynamic indices (such as the Bentley-Saxe logarithmic forest or self-balancing trees for sliding-window maps).

Who it’s for

It is primarily for C++ developers working with point clouds, robotics, and N-dimensional datasets who require exact nearest-neighbor searches with minimal memory and CPU overhead.

Highlights

  • Header-only: No compilation or installation required; just include the header file.
  • Exact Search: Returns exact nearest neighbors by default, with an optional approximate mode.
  • Manifold Support: Supports exact nearest-neighbor search on compile-time product manifolds (e.g., SO(2), SO(3), SE(2), SE(3), unit spheres, and tori) using C++17.
  • Dynamic Indices: Provides incremental and dynamic KD-tree indices for datasets that change over time, such as LiDAR maps.
  • Memory Efficient: Accesses data directly via adaptors rather than copying the entire dataset.
  • C++ Standard Support: Core Euclidean functionality is C++11; manifold metrics require C++17.

Related

  • Project
    stefankoegl/kdtree

    A simple Python implementation of a kd-tree for constructing, modifying, and searching multi-dimensional points, specifically for nearest-neighbor queries.

  • Project
    google-research/kauldron

    Kauldron is a modular machine learning training library designed to increase research velocity by providing a flexible glue layer for datasets, models, and optimizers.

  • Project
    stillwater-sc/universal

    Header‑only C++ library offering many custom numeric types (half, bfloat16, posit, fixed‑point, etc.) for mixed‑precision AI, DSP, HPC, and embedded work. Provides plug‑in replacements for built‑in types, extensive tests, Docker image, and documentation; suitable for prototyping low‑precision deep‑learning kernels and numerical research.

  • Project
    uxlfoundation/oneDNN

    A cross-platform library of optimized deep learning operations that serves as an acceleration layer for frameworks like PyTorch and TensorFlow across various CPUs and GPUs.

  • Project
    nmslib/hnswlib

    hnswlib is a header‑only C++ library (with Python bindings) that implements the Hierarchical Navigable Small World (HNSW) algorithm for fast approximate nearest‑neighbor search. It supports incremental insertions, deletions, custom distance metrics, multithreading, and a no‑exception build mode. Install via `pip install hnswlib` or from source, then create an `Index`, add vectors, tune `ef` for query accuracy, and query with `knn_query`. Suitable for embedding‑based retrieval, recommendation, or any high‑dimensional vector search task.