Suppose I have multi-dimensional datasets, which have many vectors as data. I am writing an algorithm which needs to do k nearest neighbour searches for all those vectors - classical KNN. However, during my algorithm I add new vectors to the overall dataset and need to include those new vectors into my KNN search. I want to do that efficiently. I looked into KD tree and ball tree of scikit-learn, but they don't allow inserts (by the nature of the concepts). I am not sure whether SR tree or R tree would provide inserts, but in any case, I was not able to find a python implementation for data beyond 3D.

Regarding the search I am fine with either the query "give me the closest vector" (so 1-NN) or "give me all vectors that are closer then radius".

  • $\begingroup$ KD tree is only more efficient than exhaustive NN search if you have relatively low dimensions. Maybe you can get away with doing exhaustive search which should make it easier to insert new observations. $\endgroup$ – David Ernst Aug 25 '17 at 22:26
  • $\begingroup$ @user7019377: For now I am only using data with up to 4 dimensions. What I am currently doing is, I rebuild the kd-tree every time the number of available data vectors doubles. That a part of the vectors thus is not included in the search is sad speed-wise, but does not hurt the results themselves. Using a tree that supports updates would mean, I could use all available vectors to do my speed improvements. The lesson here is that using kd-tree that way is faster than exhaustive search (I did experiments). I hope that using a tree that can to inserts, improves on speed further. $\endgroup$ – Make42 Aug 26 '17 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.