KristofferC / NearestNeighbors.jl

High performance nearest neighbor data structures (KDTree and BallTree) and algorithms for Julia.
Other
413 stars 65 forks source link

previous nearest neighbors in set of ordered points #109

Open joeguinness opened 4 years ago

joeguinness commented 4 years ago

Hello, I am wondering if it is possible for me to modify some of the functions in this package to solve the following problem: let x_1, x_2, ..., x_n be an ordered set of points in a euclidean space (e.g. x_1 = (4.7, 3.2, 1.6) ). For each i, I would like to find the nearest neighbors to x_i from the set of points (x_1, x2, ..., x{i-1}), that is, from the set of points that come previous to x_i in the ordering. The application is called Vecchia's approximation, a method for approximating likelihoods for Gaussian process models.

A naive way would be to recompute the tree from (x_1,...,x_i) for each i, and select the nearest neighbors to x_i from that tree. But that would be wasteful, and I'm hoping I can compute the tree once at the beginning and re-use the same tree.

Any help would be appreciated. I'm somewhat new to julia but have lots of experience writing R code and moderate experience in C++.