downflux/go-kd

Implement (1+ε)-ANN

Opened this issue · 0 comments

KNN is very slow, due to

  • the thrashing caused by the internal priority queue constantly attempting to maintain order for large number of points, and
  • the large number of nodes visited for large N

Running a KNN performance test in 10M randomly generated 10D points and searching for 50K points takes ~2s and looks to be irreducible, barring some minor memory optimization.

We should look into offering ANN as an alternative when performance is critical.