Implement (1+ε)-ANN
Opened this issue · 0 comments
minkezhang commented
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.