<p><a href="https://github.com/mentekid" class="user-mention">@mentekid</a> <a href="https://github.com/MarcosPividori" class="user-mention">@MarcosPividori</a> <a href="https://github.com/lozhnikov" class="user-mention">@lozhnikov</a>: 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:</p>
<pre><code>◈ ryan@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@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
</code></pre>
<p>The only real question I have, is, the command-line programs take the parameter name <code>-t octree</code> for octrees, but the other trees are <code>-t kd</code>, <code>-t r</code>, and so forth. Maybe should I have gone with <code>-t oct</code> or <code>-t oc</code> to make things similar across all trees?</p>
<p>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.</p>
<hr>
<h4>You can view, comment on, or merge this pull request online at:</h4>
<p> <a href='https://github.com/mlpack/mlpack/pull/790'>https://github.com/mlpack/mlpack/pull/790</a></p>
<h4>Commit Summary</h4>
<ul>
<li>First commit, no code yet; just moving systems.</li>
<li>Minor updates.</li>
<li>Intermediate checkin so I can move systems easily.</li>
<li>Update some minor documentation and const correctness.</li>
<li>Fix typo.</li>
<li>Add some simple octree tests.</li>
<li>Add traits and main include file.</li>
<li>Add copy, move, and serialization, plus tests for the octree.</li>
<li>Add traversers for octree.</li>
<li>Add tested support to KNN/KFN for octree.</li>
<li>Add octree to RangeSearch and RASearch.</li>
<li>Merge branch 'octree' of https://github.com/rcurtin/mlpack into octree</li>
</ul>
<h4>File Changes</h4>
<ul>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-0">src/mlpack/core/tree/CMakeLists.txt</a>
(8)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-1">src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp</a>
(8)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-2">src/mlpack/core/tree/binary_space_tree/traits.hpp</a>
(2)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-3">src/mlpack/core/tree/octree.hpp</a>
(17)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-4">src/mlpack/core/tree/octree/dual_tree_traverser.hpp</a>
(78)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-5">src/mlpack/core/tree/octree/dual_tree_traverser_impl.hpp</a>
(147)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-6">src/mlpack/core/tree/octree/octree.hpp</a>
(430)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-7">src/mlpack/core/tree/octree/octree_impl.hpp</a>
(854)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-8">src/mlpack/core/tree/octree/single_tree_traverser.hpp</a>
(53)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-9">src/mlpack/core/tree/octree/single_tree_traverser_impl.hpp</a>
(67)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-10">src/mlpack/core/tree/octree/traits.hpp</a>
(66)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-11">src/mlpack/methods/neighbor_search/kfn_main.cpp</a>
(9)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-12">src/mlpack/methods/neighbor_search/knn_main.cpp</a>
(9)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-13">src/mlpack/methods/neighbor_search/ns_model.hpp</a>
(13)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-14">src/mlpack/methods/neighbor_search/ns_model_impl.hpp</a>
(27)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-15">src/mlpack/methods/range_search/range_search_main.cpp</a>
(8)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-16">src/mlpack/methods/range_search/rs_model.cpp</a>
(104)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-17">src/mlpack/methods/range_search/rs_model.hpp</a>
(6)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-18">src/mlpack/methods/range_search/rs_model_impl.hpp</a>
(14)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-19">src/mlpack/methods/rann/krann_main.cpp</a>
(11)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-20">src/mlpack/methods/rann/ra_model.hpp</a>
(6)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-21">src/mlpack/methods/rann/ra_model_impl.hpp</a>
(176)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-22">src/mlpack/tests/CMakeLists.txt</a>
(1)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-23">src/mlpack/tests/knn_test.cpp</a>
(12)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-24">src/mlpack/tests/krann_search_test.cpp</a>
(6)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-25">src/mlpack/tests/octree_test.cpp</a>
(342)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-26">src/mlpack/tests/range_search_test.cpp</a>
(12)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/790/files#diff-27">src/mlpack/tests/ub_tree_test.cpp</a>
(4)
</li>
</ul>
<h4>Patch Links:</h4>
<ul>
<li><a href='https://github.com/mlpack/mlpack/pull/790.patch'>https://github.com/mlpack/mlpack/pull/790.patch</a></li>
<li><a href='https://github.com/mlpack/mlpack/pull/790.diff'>https://github.com/mlpack/mlpack/pull/790.diff</a></li>
</ul>
<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/pull/790">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFLSZEgqoefl6bqs3s_5fm7CVWQCNks5qtX_ZgaJpZM4KFuuW">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFKaq79aoCfuobsQuPzZLfqe47KJsks5qtX_ZgaJpZM4KFuuW.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
<link itemprop="url" href="https://github.com/mlpack/mlpack/pull/790"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>
<script type="application/json" data-scope="inboxmarkup">{"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/mlpack/mlpack","title":"mlpack/mlpack","subtitle":"GitHub repository","main_image_url":"https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/mlpack/mlpack"}},"updates":{"snippets":[{"icon":"DESCRIPTION","message":"Octree (#790)"}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/790"}}}</script>