<p><a href="https://github.com/sumedhghaisas" class="user-mention">@sumedhghaisas</a><br>
Hi, this pull request include the implementation of approximate neighbor search. Some details:</p>

<ul>
<li>I implemented the modification on the prune rule to do approximate neighbor search. Mainly, I modified the code to include an epsilon value, which is considered by rule_type.</li>
<li>We can use the epsilon to make a tighter bound B_1, (not B_2). I implemented a Relax(..) function, included in sort policies, to modify a given value according to epsilon. When doing dual tree search, the best between the modified B_1 bound and the original B_2 bound is chosen.</li>
<li>I updated the command line tools to include an extra option "-e", to specify the relative error (default value: 0).</li>
<li>Then, I added many test cases. I did that in different files, because I think knn_test.hpp and kfn_test.hpp are too big to include more test cases. I thought we could maintain separated files:

<ul>
<li>knn_test.hpp/kfn_test.hpp for exact neighbor search tests.</li>
<li>aknn_test.hpp/akfn_test.hpp for approximate neighbor search tests.</li>
</ul>
</li>
<li>I defined a new macro to check the relative error in the tests: REQUIRE_RELATIVE_ERR(..). I included it in the file: old_boost_test_definitions.hpp. If you agree, I would like to change it to a new name like: test_tools.hpp, where we could include useful defines in the future as I do right now, not only old boost definitions.
Every feedback is welcome,
Thanks!</li>
</ul>

<hr>

<h4>You can view, comment on, or merge this pull request online at:</h4>
<p>&nbsp;&nbsp;<a href='https://github.com/mlpack/mlpack/pull/684'>https://github.com/mlpack/mlpack/pull/684</a></p>

<h4>Commit Summary</h4>
<ul>
  <li>Modify KNN/KFN to include Approximate Neighbor Search.</li>
  <li>Add tests for approximate Nearest Neighbor Search.</li>
  <li>Add tests for approximate Furthest Neighbor Search.</li>
  <li>Replace CLOSE by CLOSE_FRACTION.</li>
  <li>Properly check relative error.</li>
</ul>

<h4>File Changes</h4>
<ul>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-0">src/mlpack/methods/neighbor_search/kfn_main.cpp</a>
    (12)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-1">src/mlpack/methods/neighbor_search/knn_main.cpp</a>
    (14)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-2">src/mlpack/methods/neighbor_search/neighbor_search.hpp</a>
    (15)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-3">src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp</a>
    (32)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-4">src/mlpack/methods/neighbor_search/neighbor_search_rules.hpp</a>
    (4)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-5">src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp</a>
    (10)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-6">src/mlpack/methods/neighbor_search/ns_model.hpp</a>
    (6)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-7">src/mlpack/methods/neighbor_search/ns_model_impl.hpp</a>
    (63)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-8">src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp</a>
    (17)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-9">src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp</a>
    (15)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-10">src/mlpack/tests/CMakeLists.txt</a>
    (2)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-11">src/mlpack/tests/akfn_test.cpp</a>
    (241)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-12">src/mlpack/tests/aknn_test.cpp</a>
    (397)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/684/files#diff-13">src/mlpack/tests/old_boost_test_definitions.hpp</a>
    (5)
  </li>
</ul>

<h4>Patch Links:</h4>
<ul>
  <li><a href='https://github.com/mlpack/mlpack/pull/684.patch'>https://github.com/mlpack/mlpack/pull/684.patch</a></li>
  <li><a href='https://github.com/mlpack/mlpack/pull/684.diff'>https://github.com/mlpack/mlpack/pull/684.diff</a></li>
</ul>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<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/684">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFG2C8U12-YZhItLQGv0zXVfzX8tSks5qJOL5gaJpZM4IvhJu">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFMQIDsDHoaKq43OTqWqCdtgkVo9eks5qJOL5gaJpZM4IvhJu.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/684"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>