stefankoegl/kdtree — pull request #19 by cyberjoac (2014-06-17 10:34:49+00:00)
Title: Correcting the kNN functionality.

## Abstract
Corrected the kNN functionality: Using a bounded priority queue (with bound=k) in order to save the k best results so far. I'm not sure but it looks to me a more elegant and more efficient solution (the whole logic of inserting and sorting is encapsulated inside the BoundedPriorityQueue class).
It's your call if you think that you should keep the results logic as it was or use mine with the BoundedPriorityQueue logic.
This has to do more with code elegance than pure functionality.

## Functionality
Regarding functionality, the two most important edits are the following:
#### First edit
```
#get new best
- bestNode = next(iter(sorted(results, key=get_dist))) # It seems to me that you are fetching the best-node,
#which is having the smallest distance in the results list, and not habing the BIGGEST distance in the
#results list.

+ maxDist = results.max() # Instead we should fetch the MAX distance so far in the
# results list and compare it.
```
(P.S: I'm having a hard time justifying you the correctness of the algorithm because there are a lot of details to follow along) so it would seriously help a great deal to go over
this paper (less than half an hour, very clear and concise) in order to understand the logic here. (especially p.10-11)

#### Second Edit
```
+ if lineIntersects or results.size() < k
```
The results.size() < k (BPQ isn't full) is critical because if we prune out parts of the tree before we have made at least k guesses, we might accidentally throw out one of the closest points.

## Remarks
I'm a recently graduated computer scientist so I'm sure I could improve tons about coding style (for sure the tests don't look so great) and clearness but I tried to be as clear as possible.

I pushed my test files in order for you to test the functionality before/after the change but it's your choice if you want to include them in the new version.
I discovered that the results I got were inconsistent when running kNN so I investigated it and I believe I identified a problem in the algorithm logic.
Among others, it would be possible that I insert 15 nodes, searches for the 10 closest nodes, and receives only 5. I tried to describe above the reasons why I believe it did that.

I'd be happy to hear if I could make any improvements in my workflow for collaborating with open-source code, because it's my first time doing so and for sure I have tons to learn from you.

Maybe we could make a Skype sometimes.

According to the tests I ran, the functionality is now correct, but you should double-check that I didn't break anything in your code by making those changes..

I owe you a great deal anyway for this great kDD implementation, and I hope you will consider my pull request.

Best regards.