[mlpack-git] [mlpack/mlpack] Approximate Neighbor Search for Dual tree algorithms. (#684)

[MarcosPividori]

@sumedhghaisas
Hi, this pull request include the implementation of approximate neighbor search. Some details:
+ 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.
+ 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.
+ I updated the command line tools to include an extra option "-e", to specify the relative error (default value: 0).
+ 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:
  - knn_test.hpp/kfn_test.hpp for exact neighbor search tests.
  - aknn_test.hpp/akfn_test.hpp for approximate neighbor search tests.
+ 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!
You can view, comment on, or merge this pull request online at:

  https://github.com/mlpack/mlpack/pull/684

-- Commit Summary --

  * Modify KNN/KFN to include Approximate Neighbor Search.
  * Add tests for approximate Nearest Neighbor Search.
  * Add tests for approximate Furthest Neighbor Search.
  * Replace CLOSE by CLOSE_FRACTION.
  * Properly check relative error.

-- File Changes --

    M src/mlpack/methods/neighbor_search/kfn_main.cpp (12)
    M src/mlpack/methods/neighbor_search/knn_main.cpp (14)
    M src/mlpack/methods/neighbor_search/neighbor_search.hpp (15)
    M src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp (32)
    M src/mlpack/methods/neighbor_search/neighbor_search_rules.hpp (4)
    M src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp (10)
    M src/mlpack/methods/neighbor_search/ns_model.hpp (6)
    M src/mlpack/methods/neighbor_search/ns_model_impl.hpp (63)
    M src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp (17)
    M src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp (15)
    M src/mlpack/tests/CMakeLists.txt (2)
    A src/mlpack/tests/akfn_test.cpp (241)
    A src/mlpack/tests/aknn_test.cpp (397)
    M src/mlpack/tests/old_boost_test_definitions.hpp (5)

-- Patch Links --

https://github.com/mlpack/mlpack/pull/684.patch
https://github.com/mlpack/mlpack/pull/684.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/684
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160606/a9330864/attachment.html>