[mlpack-git] [mlpack/mlpack] Neighbor Search - Incorrect bound. (#642)

[MarcosPividori]

Hi Ryan,
Thank you very much for taking the time to write that proof. This is becoming really interesting!

I am not sure about:
"The ball of radius lambda(N_c) centered at the center of the node N_c lies entirely within the ball of radius lambda(N_q) centered at the center of the node N_q."
I agree that this is true for trees that consider "ballbound", but that is not true for different bounds such as "hrectbound" used in KDTrees.
The ball of radius (diagonal_of_rectangle / 2) centered at the center of a rectangle will not include the balls of the subrectangles resulting of splitting the original rectangle at the middle.

However, with actual KDTree implementation, we do not have any problem because points are only included in leaf nodes, so the optimization of using rho instead of lambda is never considered.

How are R-Trees implemented? Do they include points in non-leaf nodes? I will read about them.

I have an idea of a space tree where the B2 bound could fail. I will try to think about it and I let you know.

Thanks!

PD: A simple detail about the proof, in ecuations (8) and (9), should be (lambda(N_q) - lambda(N_c)) instead of (lambda(N_q) + lambda(N_c)). In case you want to use it in the future.

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/issues/642#issuecomment-221717687
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160525/3ae79d8f/attachment-0001.html>