Integrate DTree into BinarySpaceTree

[rcurtin]

Reported by rcurtin on 28 Jun 42549469 20:57 UTC
A density estimation tree (see methods/det) is a form of binary space tree, except that it splits differently and each node needs to hold some information about its own density.

In fact, I would say it is similar enough that a density estimation tree could actually just be a specific instantiation of a BinarySpaceTree with a different splitting mechanism and a specially constructed statistic object to hold the necessary information.

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

[palashahuja]

@rcurtin, I'd like to work on this, but I would need some help.

[thejonan]

I want to have sparse matrix enabled DET, but making this integration looks like a better step, so I'm ready to provide this help. @palashahuja, do you have any progress so far?

[thejonan]

After about two days of investigation of BinarySpaceTree I've given up doing that merge, because of these, few reasons:

• BinarySpaceTree is both quite universal, but in the same time - pretty much bound to tasks like kNN, etc. For example, the split criteria is solely bound to the Bound type, i.e. the space boundaries, which is not exactly the case in DET, where the split is based on a broader term of error.
• Also, there is a good amount of methods, related to this approach, and having nothing to do with DET's task (*Distance, *Descendants, etc.). In the same time methods a-la ComputeValue are missing as a concept.
• Some of the template arguments of BinarySpaceTree class are really making it pretty weird to provide necessary classes, being templated themselves - I know this is because of ease of providing these arguments.

So, at the end of the day, I've realized it is more like a "hack", rather than different instantiation - the value that BinarySpaceTree would bring would be comparably small to the custom implementation that DTree requires.

However, I've made the the whole DET algorithm implementation sparse-matrix enabled (Pull Request #802), so it shouldn't be difficult for this merge to happen, should someone wants to do it.

[rcurtin]

I have to agree with the last comment here, and there is no pressing need to integrate the two, so I will go ahead and close this issue.