@mentekid @MarcosPividori @lozhnikov: I wanted to implement one more tree type (the octree) before implementing SLEEC for automatic nearest neighbor search selection. Here's that implementation, maybe it is of interest. Octrees are very good for low dimensions (like 2 or 3) and can outperform kd-trees there. This implementation does:
```
◈ ryan at humungus ☃ build-nodebug ◈ $ bin/mlpack_knn -r ~/datasets/birch3.txt -k 3 -v -t octree | grep 'were\|computing_neighbors\|tree_building'
[INFO ] 1351544 node combinations were scored.
[INFO ] 2178671 base cases were calculated.
[INFO ] computing_neighbors: 0.171068s
[INFO ] tree_building: 0.365612s
◈ ryan at humungus ☃ build-nodebug ◈ $ bin/mlpack_knn -r ~/datasets/birch3.txt -k 3 -v | grep 'were\|computing_neighbors\|tree_building'
[INFO ] 1113714 node combinations were scored.
[INFO ] 2714362 base cases were calculated.
[INFO ] computing_neighbors: 0.167564s
[INFO ] tree_building: 0.040383s
```
The only real question I have, is, the command-line programs take the parameter name `-t octree` for octrees, but the other trees are `-t kd`, `-t r`, and so forth. Maybe should I have gone with `-t oct` or `-t oc` to make things similar across all trees?
If anyone spots any bugs, problems, or opportunities for improvement, I'll get them fixed quickly, otherwise I will probably let this sit for a week and then merge it in. :) My goal is for this to be part of mlpack 2.1.0.
You can view, comment on, or merge this pull request online at:
https://github.com/mlpack/mlpack/pull/790
-- Commit Summary --
* First commit, no code yet; just moving systems.
* Minor updates.
* Intermediate checkin so I can move systems easily.
* Update some minor documentation and const correctness.
* Fix typo.
* Add some simple octree tests.
* Add traits and main include file.
* Add copy, move, and serialization, plus tests for the octree.
* Add traversers for octree.
* Add tested support to KNN/KFN for octree.
* Add octree to RangeSearch and RASearch.
* Merge branch 'octree' of https://github.com/rcurtin/mlpack into octree
-- File Changes --
M src/mlpack/core/tree/CMakeLists.txt (8)
M src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp (8)
M src/mlpack/core/tree/binary_space_tree/traits.hpp (2)
A src/mlpack/core/tree/octree.hpp (17)
A src/mlpack/core/tree/octree/dual_tree_traverser.hpp (78)
A src/mlpack/core/tree/octree/dual_tree_traverser_impl.hpp (147)
A src/mlpack/core/tree/octree/octree.hpp (430)
A src/mlpack/core/tree/octree/octree_impl.hpp (854)
A src/mlpack/core/tree/octree/single_tree_traverser.hpp (53)
A src/mlpack/core/tree/octree/single_tree_traverser_impl.hpp (67)
A src/mlpack/core/tree/octree/traits.hpp (66)
M src/mlpack/methods/neighbor_search/kfn_main.cpp (9)
M src/mlpack/methods/neighbor_search/knn_main.cpp (9)
M src/mlpack/methods/neighbor_search/ns_model.hpp (13)
M src/mlpack/methods/neighbor_search/ns_model_impl.hpp (27)
M src/mlpack/methods/range_search/range_search_main.cpp (8)
M src/mlpack/methods/range_search/rs_model.cpp (104)
M src/mlpack/methods/range_search/rs_model.hpp (6)
M src/mlpack/methods/range_search/rs_model_impl.hpp (14)
M src/mlpack/methods/rann/krann_main.cpp (11)
M src/mlpack/methods/rann/ra_model.hpp (6)
M src/mlpack/methods/rann/ra_model_impl.hpp (176)
M src/mlpack/tests/CMakeLists.txt (1)
M src/mlpack/tests/knn_test.cpp (12)
M src/mlpack/tests/krann_search_test.cpp (6)
A src/mlpack/tests/octree_test.cpp (342)
M src/mlpack/tests/range_search_test.cpp (12)
M src/mlpack/tests/ub_tree_test.cpp (4)
-- Patch Links --
https://github.com/mlpack/mlpack/pull/790.patch
https://github.com/mlpack/mlpack/pull/790.diff
--
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/pull/790
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160924/8acef7e1/attachment.html>