[mlpack-git] master: For monochromatic dual-tree search, the bounds may need to be reset. (d02f7c4)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/00eccfdb0d315de3d94bfa1da84cc1dc65c8af39...c81893381e80d4ecae4283cec5fe5264bdf4f677

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

commit d02f7c456bab60685d812285f7c5ccef607ba396
Author: ryan <ryan at ratml.org>
Date:   Tue Oct 20 11:08:10 2015 -0400

    For monochromatic dual-tree search, the bounds may need to be reset.
    
    This only happens when monochromatic dual-tree search is performed twice.


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

d02f7c456bab60685d812285f7c5ccef607ba396
 .../methods/neighbor_search/neighbor_search.hpp    |  4 ++
 .../neighbor_search/neighbor_search_impl.hpp       | 46 ++++++++++++++++++++--
 2 files changed, 46 insertions(+), 4 deletions(-)

diff --git a/src/mlpack/methods/neighbor_search/neighbor_search.hpp b/src/mlpack/methods/neighbor_search/neighbor_search.hpp
index fa6a987..f1865a7 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search.hpp
@@ -301,6 +301,10 @@ class NeighborSearch
   //! The total number of scores (applicable for non-naive search).
   size_t scores;
 
+  //! If this is true, the reference tree bounds need to be reset on a call to
+  //! Search() without a query set.
+  bool treeNeedsReset;
+
   //! The NSModel class should have access to internal members.
   friend class NSModel<SortPolicy>;
 }; // class NeighborSearch
diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
index 4c7309f..68a0245 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
@@ -85,7 +85,8 @@ NeighborSearch(const MatType& referenceSetIn,
     singleMode(!naive && singleMode), // No single mode if naive.
     metric(metric),
     baseCases(0),
-    scores(0)
+    scores(0),
+    treeNeedsReset(false)
 {
   // Nothing to do.
 }
@@ -114,7 +115,8 @@ NeighborSearch(MatType&& referenceSetIn,
     singleMode(!naive && singleMode),
     metric(metric),
     baseCases(0),
-    scores(0)
+    scores(0),
+    treeNeedsReset(false)
 {
   // Nothing to do.
 }
@@ -139,7 +141,8 @@ NeighborSearch(Tree* referenceTree,
     singleMode(singleMode),
     metric(metric),
     baseCases(0),
-    scores(0)
+    scores(0),
+    treeNeedsReset(false)
 {
   // Nothing else to initialize.
 }
@@ -164,7 +167,8 @@ NeighborSearch<SortPolicy, MetricType, MatType, TreeType, TraversalType>::
     singleMode(singleMode),
     metric(metric),
     baseCases(0),
-    scores(0)
+    scores(0),
+    treeNeedsReset(false)
 {
   // Build the tree on the empty dataset, if necessary.
   if (!naive)
@@ -619,6 +623,29 @@ Search(const size_t k,
   }
   else
   {
+    // The dual-tree monochromatic search case may require resetting the bounds
+    // in the tree.
+    if (treeNeedsReset)
+    {
+      std::stack<Tree*> nodes;
+      nodes.push(referenceTree);
+      while (!nodes.empty())
+      {
+        Tree* node = nodes.top();
+        nodes.pop();
+
+        // Reset bounds of this node.
+        node->Stat().FirstBound() = SortPolicy::WorstDistance();
+        node->Stat().SecondBound() = SortPolicy::WorstDistance();
+        node->Stat().Bound() = SortPolicy::WorstDistance();
+        node->Stat().LastDistance() = 0.0;
+
+        // Then add the children.
+        for (size_t i = 0; i < node->NumChildren(); ++i)
+          nodes.push(&node->Child(i));
+      }
+    }
+
     // Create the traverser.
     TraversalType<RuleType> traverser(rules);
 
@@ -629,6 +656,9 @@ Search(const size_t k,
 
     Log::Info << rules.Scores() << " node combinations were scored.\n";
     Log::Info << rules.BaseCases() << " base cases were calculated.\n";
+
+    // Next time we perform this search, we'll need to reset the tree.
+    treeNeedsReset = true;
   }
 
   Timer::Stop("computing_neighbors");
@@ -697,6 +727,7 @@ void NeighborSearch<SortPolicy, MetricType, MatType, TreeType, TraversalType>::
   // Serialize preferences for search.
   ar & CreateNVP(naive, "naive");
   ar & CreateNVP(singleMode, "singleMode");
+  ar & CreateNVP(treeNeedsReset, "treeNeedsReset");
 
   // If we are doing naive search, we serialize the dataset.  Otherwise we
   // serialize the tree.
@@ -752,6 +783,13 @@ void NeighborSearch<SortPolicy, MetricType, MatType, TreeType, TraversalType>::
       setOwner = false;
     }
   }
+
+  // Reset base cases and scores.
+  if (Archive::is_loading::value)
+  {
+    baseCases = 0;
+    scores = 0;
+  }
 }
 
 } // namespace neighbor