[mlpack-git] master: Avoid B_2 bound for Spill Trees. (2bad753)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/0f4b25acd6aaa14294c044874ba6cc0751712baa...0a19d07bd39e6223991976474bc79671ba8aa0f0

>---------------------------------------------------------------

commit 2bad753ca4859b6b2067d60b4323dcab5438959e
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Wed Aug 17 03:34:53 2016 -0300

    Avoid B_2 bound for Spill Trees.


>---------------------------------------------------------------

2bad753ca4859b6b2067d60b4323dcab5438959e
 src/mlpack/core/tree/CMakeLists.txt                |  1 +
 src/mlpack/core/tree/spill_tree.hpp                |  1 +
 src/mlpack/core/tree/spill_tree/is_spill_tree.hpp  | 38 ++++++++++++++++++++++
 .../neighbor_search/neighbor_search_rules_impl.hpp |  5 +++
 4 files changed, 45 insertions(+)

diff --git a/src/mlpack/core/tree/CMakeLists.txt b/src/mlpack/core/tree/CMakeLists.txt
index 34dc5c7..107e56e 100644
--- a/src/mlpack/core/tree/CMakeLists.txt
+++ b/src/mlpack/core/tree/CMakeLists.txt
@@ -88,6 +88,7 @@ set(SOURCES
   space_split/space_split.hpp
   space_split/space_split_impl.hpp
   spill_tree.hpp
+  spill_tree/is_spill_tree.hpp
   spill_tree/spill_tree.hpp
   spill_tree/spill_tree_impl.hpp
   spill_tree/spill_dual_tree_traverser.hpp
diff --git a/src/mlpack/core/tree/spill_tree.hpp b/src/mlpack/core/tree/spill_tree.hpp
index b93300b..a498be5 100644
--- a/src/mlpack/core/tree/spill_tree.hpp
+++ b/src/mlpack/core/tree/spill_tree.hpp
@@ -9,6 +9,7 @@
 
 #include <mlpack/core.hpp>
 #include "bounds.hpp"
+#include "spill_tree/is_spill_tree.hpp"
 #include "spill_tree/spill_tree.hpp"
 #include "spill_tree/spill_single_tree_traverser.hpp"
 #include "spill_tree/spill_single_tree_traverser_impl.hpp"
diff --git a/src/mlpack/core/tree/spill_tree/is_spill_tree.hpp b/src/mlpack/core/tree/spill_tree/is_spill_tree.hpp
new file mode 100644
index 0000000..a9a4e35
--- /dev/null
+++ b/src/mlpack/core/tree/spill_tree/is_spill_tree.hpp
@@ -0,0 +1,38 @@
+/**
+ * @file is_spill_tree.hpp
+ *
+ * Definition of IsSpillTree.
+ */
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_IS_SPILL_TREE_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_IS_SPILL_TREE_HPP
+
+#include "spill_tree.hpp"
+
+namespace mlpack {
+namespace tree /** Trees and tree-building procedures. */ {
+
+// Useful struct when specific behaviour for SpillTrees is required.
+template<typename TreeType>
+struct IsSpillTree
+{
+  static const bool value = false;
+};
+
+// Specialization for SpillTree.
+template<typename MetricType,
+         typename StatisticType,
+         typename MatType,
+         template<typename HyperplaneMetricType>
+            class HyperplaneType,
+         template<typename SplitMetricType, typename SplitMatType>
+            class SplitType>
+struct IsSpillTree<tree::SpillTree<MetricType, StatisticType, MatType,
+    HyperplaneType, SplitType>>
+{
+  static const bool value = true;
+};
+
+} // namespace tree
+} // namespace mlpack
+
+#endif
diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
index 01dd892..df4913e 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
@@ -9,6 +9,7 @@
 
 // In case it hasn't been included yet.
 #include "neighbor_search_rules.hpp"
+#include <mlpack/core/tree/spill_tree/is_spill_tree.hpp>
 
 namespace mlpack {
 namespace neighbor {
@@ -456,6 +457,10 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::
 
   worstDistance = SortPolicy::Relax(worstDistance, epsilon);
 
+  // We can't consider B_2 for Spill Trees.
+  if (tree::IsSpillTree<TreeType>::value)
+    return worstDistance;
+
   if (SortPolicy::IsBetter(worstDistance, bestDistance))
     return worstDistance;
   else