cover tree could rearrange descendants in memory for faster accesses

[rcurtin]

Reported by rcurtin on 14 Dec 43355870 02:33 UTC
Right now, the dataset which is given to the cover tree when it is built does not move any points around in memory; it simply holds references to the points in the tree.

In situations where the descendants are looped over (with NumDescendants() and Descendant()), this is far from optimal and could be much faster if the points had been arranged in memory such that Descendant(i) just returns i plus some constant (the point held by that node).

This would take some refactoring of the cover tree class but should provide decent speedup.

Migrated-From: http://trac.research.cc.gatech.edu/fastlab/ticket/285

[na1taneja2821]

Hi,
I was going through this issue to solve it. As already stated in the issue, the node stores the references to the points. I just want to clarify, whether we can rearrange the points in the dataset itself (so that the references can be accessed by adding the constant) or whether there is a need to maintain another memory block for accessing the points?

[rcurtin]

Hi Naman,

Take a look at the code for BinarySpaceTree (src/mlpack/core/tree/binary_space_tree). The BinarySpaceTree, because it rearranges descendants, must make a copy of the const data matrix, or otherwise the data matrix must be passed as an rvalue reference. You can make the same modification for the cover tree.

[na1taneja2821]

Hi Ryan,
Sorry for the late response, had been busy with the practical exams. I have gone through the code for cover tree (and I must say it is quite well written). I have made certain changes to solve the issue and currently debugging it. I will open the pull request soon.