lsh_search.hpp
Go to the documentation of this file.00001
00038 #ifndef __MLPACK_METHODS_NEIGHBOR_SEARCH_LSH_SEARCH_HPP
00039 #define __MLPACK_METHODS_NEIGHBOR_SEARCH_LSH_SEARCH_HPP
00040
00041 #include <mlpack/core.hpp>
00042 #include <vector>
00043 #include <string>
00044
00045 #include <mlpack/core/metrics/lmetric.hpp>
00046 #include <mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp>
00047
00048 namespace mlpack {
00049 namespace neighbor {
00050
00058 template<typename SortPolicy = NearestNeighborSort>
00059 class LSHSearch
00060 {
00061 public:
00083 LSHSearch(const arma::mat& referenceSet,
00084 const arma::mat& querySet,
00085 const size_t numProj,
00086 const size_t numTables,
00087 const double hashWidth = 0.0,
00088 const size_t secondHashSize = 99901,
00089 const size_t bucketSize = 500);
00090
00111 LSHSearch(const arma::mat& referenceSet,
00112 const size_t numProj,
00113 const size_t numTables,
00114 const double hashWidth = 0.0,
00115 const size_t secondHashSize = 99901,
00116 const size_t bucketSize = 500);
00117
00136 void Search(const size_t k,
00137 arma::Mat<size_t>& resultingNeighbors,
00138 arma::mat& distances,
00139 const size_t numTablesToSearch = 0);
00140
00141 private:
00155 void BuildHash();
00156
00168 void ReturnIndicesFromTable(const size_t queryIndex,
00169 arma::uvec& referenceIndices,
00170 size_t numTablesToSearch);
00171
00179 double BaseCase(const size_t queryIndex, const size_t referenceIndex);
00180
00193 void InsertNeighbor(const size_t queryIndex, const size_t pos,
00194 const size_t neighbor, const double distance);
00195
00196 private:
00198 const arma::mat& referenceSet;
00199
00201 const arma::mat& querySet;
00202
00204 const size_t numProj;
00205
00207 const size_t numTables;
00208
00210 std::vector<arma::mat> projections;
00211
00213 arma::mat offsets;
00214
00216 double hashWidth;
00217
00219 const size_t secondHashSize;
00220
00222 arma::vec secondHashWeights;
00223
00225 const size_t bucketSize;
00226
00228 metric::SquaredEuclideanDistance metric;
00229
00231 arma::Mat<size_t> secondHashTable;
00232
00235 arma::Col<size_t> bucketContentSize;
00236
00239 arma::Col<size_t> bucketRowInHashTable;
00240
00242 arma::mat* distancePtr;
00243
00245 arma::Mat<size_t>* neighborPtr;
00246 };
00247
00248 };
00249 };
00250
00251
00252 #include "lsh_search_impl.hpp"
00253
00254 #endif