KDTree is not reliably returning nearest neighbor 100% of the time.
Closed this issue · 1 comments
My colleague and I have been using your KDTree implementation. However, we've found that, contrary to the definition of KDTree, this implementation does not produce the nearest neighbor 100% of the time.
We're attaching some code we used to show this, the link is at the bottom of this Issue. Here are the results that we obtained when running the code:
Total number of iterations ran: 50
Accuracy (tested with 50 datasets per iter) = 96.84 %. Avg. Total Number Correct: 48 / 50
Accuracy (tested with 100 datasets per iter) = 97.24 %. Avg. Total Number Correct: 97 / 100
Accuracy (tested with 200 datasets per iter) = 95.93 %. Avg. Total Number Correct: 191 / 200
Accuracy (tested with 300 datasets per iter) = 98.2267 %. Avg. Total Number Correct: 294 / 300
Accuracy (tested with 400 datasets per iter) = 96.9 %. Avg. Total Number Correct: 387 / 400
Accuracy (tested with 500 datasets per iter) = 99.744 %. Avg. Total Number Correct: 498 / 500
Accuracy (tested with 600 datasets per iter) = 98.4433 %. Avg. Total Number Correct: 590 / 600
Accuracy (tested with 700 datasets per iter) = 97.6029 %. Avg. Total Number Correct: 683 / 700
Accuracy (tested with 800 datasets per iter) = 97.6375 %. Avg. Total Number Correct: 781 / 800
Accuracy (tested with 900 datasets per iter) = 98.92 %. Avg. Total Number Correct: 890 / 900
Accuracy (tested with 1000 datasets per iter) = 99.822 %. Avg. Total Number Correct: 998 / 1000
Accuracy (tested with 2000 datasets per iter) = 99.641 %. Avg. Total Number Correct: 1992 / 2000
Thanks for the bug report!
I fixed the code and it now passes the test, so I'm closing the issue.