NearestNeighbors.jl

A PeriodicTree wraps an existing KDTree, BallTree, or BruteTree to handle periodic domains. This is essential for simulations where points wrap around boundaries.

Constructor: PeriodicTree(tree, bounds_min, bounds_max)

• bounds_min/bounds_max: Vectors defining the periodic domain. Use Inf in bounds_max for dimensions that are not periodic.

Mixed Dimensions: You can define a domain where some dimensions are periodic and others are infinite (non-periodic) by using Inf in the bounds_max vector.

using NearestNeighbors, StaticArrays

# 2D domain: x-periodic, y-infinite
data = [SVector(1.0, 2.0), SVector(9.0, 8.0)]
kdtree = KDTree(data)
ptree = PeriodicTree(kdtree, [0.0, 0.0], [10.0, Inf])

# Query near x-boundary finds wrapped neighbor
query = [0.5, 3.0]
idxs, dists = knn(ptree, query, 1)

If you need to rebuild a tree repeatedly from updated data (e.g., in a simulation), use the mutating constructors KDTree!, BallTree!, or BruteTree!. These recycle the internal storage of the previous tree to avoid new allocations.

Warning: The old tree is invalidated by the call and will throw an error if used afterwards. The points provided must be an array independent of the old tree's internal storage.

tree = KDTree(points; leafsize = 10)
# ... update points ...
tree = KDTree!(tree, points) # rebuilds, reusing the old tree's storage

When datasets are too large to fit in memory, use DataFreeTree to build a tree that stores only the indexing structures without copying the actual data. This is often used in conjunction with Mmap.mmap to access data from disk.

To use a DataFreeTree for look-ups, you must first re-link it to the data using injectdata(dftree, data), which returns a standard tree (e.g., a KDTree) that can be used with knn() or other search functions.

using Mmap
using NearestNeighbors

# 1. Map large data from disk
dim = 2
n = 10_000_000_000
data = Mmap.mmap("data.bin", Matrix{Float32}, (dim, n))

# 2. Create a tree that doesn't copy the data
dftree = DataFreeTree(KDTree, data)

# 3. Re-link to data to perform searches
tree = injectdata(dftree, data)
knn(tree, data[:, 1], 3)

You can inspect the spatial boundaries covered by any node using treeregion(node). The type of region returned depends on the tree type:

• KDTree: Returns a HyperRectangle. Access boundaries via .mins and .maxes.
• BallTree: Returns a HyperSphere. Access the center via .center and the radius via .r.

# Inspecting KDTree regions
kdtree = KDTree(rand(2, 100))
root = treeroot(kdtree)
for node in PreOrderDFS(root)
    rect = treeregion(node)  # HyperRectangle
    println("X: [", rect.mins[1], ", ", rect.maxes[1], "]")
end

# Inspecting BallTree regions
balltree = BallTree(rand(2, 100))
root = treeroot(balltree)
for node in PostOrderDFS(root)
    sphere = treeregion(node)  # HyperSphere
    println("center=", sphere.center, ", radius=", sphere.r)
end

For performance-critical applications, use the package's built-in custom walkers instead of AbstractTrees.jl. These are significantly more efficient as they avoid the overhead of the generic interface.

Available optimized walkers:

• preorder(tree): Fast pre-order traversal.
• postorder(tree): Fast post-order traversal.
• leaves(tree): Fastest method for iterating only over leaf nodes.

using NearestNeighbors

tree = KDTree(rand(3, 10000))

# Pre-order traversal (faster than AbstractTrees.PreOrderDFS)
for node in preorder(tree)
    # node is a TreeNode
end

# Post-order traversal
for node in postorder(tree)
    # process children before parent
end

# Direct leaf iteration (fastest for leaf-only access)
for node in leaves(tree)
    pts = leafpoints(node)
    # process leaf points
end

KDTree and BallTree support parallel construction. By default, parallel building is enabled if Threads.nthreads() > 1. You can explicitly control this with the parallel keyword.

To enable multiple threads, start Julia with julia --threads=N.

# Parallel by default when multiple threads available
kdtree = KDTree(data)

# Explicitly disable parallel building
kdtree_seq = KDTree(data; parallel=false)

Use the following constructors to build trees. Data can be an nd × np matrix or a Vector of vectors with fixed dimensionality.

• KDTree(data, metric; leafsize, reorder)
• BallTree(data, metric; leafsize, reorder)
• BruteTree(data; leafsize, reorder) (Note: leafsize and reorder are unused for BruteTree)
• PeriodicTree(tree, bounds_min, bounds_max)

Parameters:

• metric: A Metric from Distances.jl. Defaults to Euclidean.
• leafsize: Number of points at which to stop splitting (default 25). Affects the trade-off between traversal speed and metric evaluation.
• reorder: If true (default), rearranges points to improve cache locality during queries (creates a copy of data).
• bounds_min/bounds_max: Vectors defining the periodic domain. Use Inf in bounds_max for non-periodic dimensions.

Find all neighbors within a specific radius r of given point(s).

Methods:

• inrange(tree, point[s], radius) -> idxs (Returns indices only)
• inrange!(idxs, tree, point, radius) (Updates existing idxs array)
• inrangecount(tree, point, radius) (Returns the count of neighbors without allocating index arrays)

Self-Pair Searches: To find all pairs of points within a tree that are within a given radius of each other, use:

• inrange_pairs(tree, radius) -> pairs (Returns a vector of tuples (i, j) where i < j).

using NearestNeighbors
data = rand(3, 10^4)
r = 0.05
point = rand(3)

balltree = BallTree(data)
idxs = inrange(balltree, point, r)

# Using inrangecount to avoid allocations
count = inrangecount(balltree, point, r)

# Finding pairs within radius
kdtree = KDTree(data)
pairs = inrange_pairs(kdtree, 0.1)

You can create a BallTree by providing a matrix of points and a distance metric. You can also specify a leafsize to control the maximum number of points in a leaf node.

Example:

using NearestNeighbors
using StableRNGs

rng = StableRNG(42)
# Create a BallTree with 100 2D points using Euclidean distance and a leafsize of 10
tree = BallTree(rand(rng, 2, 100), Euclidean(); leafsize = 10)