Is it possible to update NearestNeighbors.jl trees after construction?

General Usage
, ,
1

Is it possible to update the data in a tree after construction? Say we need to add more points to the tree, how to push! or append!? I’ve read the documentation and there is no example for that. By reading the source code I couldn’t find it either.

I’ve opened an issue in the GitHub repository to track it over there as well, in case anyone knows a solution: Documentation for tree updates? · Issue #244 · KristofferC/NearestNeighbors.jl · GitHub

2

Kristoffer answered on GitHub. Not possible by design.

3

Just to mention that the complementary package AdaptiveKDTrees.jl seems to have that functionality.

4

@juliohm, FYI: I don’t know what your exact task is, but I wrote a small jll package for using kiddo, a rust package that allows for dynamic trees. In plenty of benchmarks, it appears to be the fastest tree library available. For a pure Julia solution, I use HNSW.jl for the dynamic lookups, although these are not exact/deterministic.

I have an extension for Vecchia.jl. The speedups for specifying the conditioning sets can be pretty significant:

julia> using BenchmarkTools, Vecchia, StaticArrays

julia> kernel(x, y, params) = exp(-norm(x-y)/params[2])
kernel (generic function with 1 method)

julia> pts = rand(SVector{2,Float64}, 50_000);

julia> @btime VecchiaApproximation($pts, kernel; conditioning=$(KNNConditioning(30))); # HNSW.jl
  1.606 s (4763276 allocations: 1.09 GiB)

julia> using sequentialknn_jll
 │ Package sequentialknn_jll not found, but a package named sequentialknn_jll is available from a registry. 
 │ Install package?
 │   (jl_Q8Qptm) pkg> add sequentialknn_jll 
 └ (y/n/o) [y]: 
   Resolving package versions...
    Updating `/tmp/jl_Q8Qptm/Project.toml`
  [a3d66c5c] + sequentialknn_jll v0.2.0+0
    Updating `/tmp/jl_Q8Qptm/Manifest.toml`
  [692b3bcd] + JLLWrappers v1.8.0
  [94ce4f54] + Libiconv_jll v1.18.0+0
  [a3d66c5c] + sequentialknn_jll v0.2.0+0
[ Info: Precompiling VecchiasequentialknnExt [7df10478-612b-5f95-b980-c0b68bb95406](cache misses: wrong dep version loaded (2))
Precompiling Vecchia → VecchiasequentialknnExt finished.
  1 dependency successfully precompiled in 1 seconds. 20 already precompiled.

julia> @btime VecchiaApproximation($pts, kernel; conditioning=$(KNNConditioning(30)));
[ Info: Using accelerated sequentialknn_jll methods...
  97.890 ms (200089 allocations: 47.00 MiB)

If this or other functionality from kiddo might be useful to you, I would be happy to participate in expanding that interface and jll. Longer term, it would be cool to have a Julia-native solution that accepted as wide a range of distance metrics as possible, but I think Kristoffer, who I won’t @ because I’ve annoyed him enough about this stuff, has explained would require basically a clean re-write to try and specialize on. So that seems like a longer term project.