KristofferC/NearestNeighbors.jl

What it solves

NearestNeighbors.jl provides efficient ways to find the closest points in a dataset, a fundamental operation for many scientific simulations and machine learning tasks. It handles the challenge of searching through millions of points without having to compare every single point to every other point (brute force), which would be too slow for large datasets.

How it works

The package implements several spatial partitioning structures called "trees" that organize data points into a hierarchy of regions:

• KDTree: Splits data using axis-aligned planes, ideal for low-dimensional data.
• BallTree: Uses hyperspheres to group points, making it better for higher dimensions and custom distance metrics.
• BruteTree: A simple linear search used as a baseline.
• PeriodicTree: A wrapper that allows searches to "wrap around" the edges of a defined boundary, which is critical for physics simulations.

It supports parallel construction of trees to speed up setup time and provides mutating constructors (like KDTree!) to reuse memory when data is updated frequently.

Who it’s for

This tool is designed for researchers and developers using Julia who need to perform fast k-nearest neighbor (kNN) or range searches in multi-dimensional space.

Highlights

• Multiple Tree Types: Choose between KD-Trees and Ball-Trees based on your data dimensionality and metric.
• Periodic Boundaries: Built-in support for periodic domains via PeriodicTree.
• Memory Efficiency: Includes DataFreeTree for handling datasets larger than available RAM by using on-disk memory mapping.
• High Performance: Supports multi-threaded tree construction and provides optimized tree traversal walkers for debugging and visualization.