47#ifndef MLPACK_METHODS_NEIGHBOR_SEARCH_LSH_SEARCH_HPP
48#define MLPACK_METHODS_NEIGHBOR_SEARCH_LSH_SEARCH_HPP
70 typename MatType = arma::mat
98 const arma::cube& projections,
99 const double hashWidth = 0.0,
100 const size_t secondHashSize = 99901,
101 const size_t bucketSize = 500);
126 const size_t numProj,
127 const size_t numTables,
128 const double hashWidth = 0.0,
129 const size_t secondHashSize = 99901,
130 const size_t bucketSize = 500);
192 const size_t numProj,
193 const size_t numTables,
194 const double hashWidth = 0.0,
195 const size_t secondHashSize = 99901,
196 const size_t bucketSize = 500,
197 const arma::cube& projection = arma::cube());
222 arma::Mat<size_t>& resultingNeighbors,
223 arma::mat& distances,
224 const size_t numTablesToSearch = 0,
247 arma::Mat<size_t>& resultingNeighbors,
248 arma::mat& distances,
249 const size_t numTablesToSearch = 0,
262 const arma::Mat<size_t>& realNeighbors);
270 template<
typename Archive>
271 void serialize(Archive& ar,
const unsigned int version);
285 const arma::mat&
Offsets()
const {
return offsets; }
295 {
return secondHashTable; }
304 Train(referenceSet, numProj, numTables, hashWidth, secondHashSize,
305 bucketSize, projTables);
324 template<
typename VecType>
325 void ReturnIndicesFromTable(
const VecType& queryPoint,
326 arma::uvec& referenceIndices,
327 size_t numTablesToSearch,
328 const size_t T)
const;
343 void BaseCase(
const size_t queryIndex,
344 const arma::uvec& referenceIndices,
346 arma::Mat<size_t>& neighbors,
347 arma::mat& distances)
const;
363 void BaseCase(
const size_t queryIndex,
364 const arma::uvec& referenceIndices,
366 const MatType& querySet,
367 arma::Mat<size_t>& neighbors,
368 arma::mat& distances)
const;
384 void GetAdditionalProbingBins(
const arma::vec& queryCode,
385 const arma::vec& queryCodeNotFloored,
387 arma::mat& additionalProbingBins)
const;
396 double PerturbationScore(
const std::vector<bool>& A,
397 const arma::vec& scores)
const;
406 bool PerturbationShift(std::vector<bool>& A)
const;
416 bool PerturbationExpand(std::vector<bool>& A)
const;
425 bool PerturbationValid(
const std::vector<bool>& A)
const;
428 MatType referenceSet;
436 arma::cube projections;
445 size_t secondHashSize;
448 arma::vec secondHashWeights;
455 std::vector<arma::Col<size_t>> secondHashTable;
459 arma::Col<size_t> bucketContentSize;
463 arma::Col<size_t> bucketRowInHashTable;
466 size_t distanceEvaluations;
469 typedef std::pair<double, size_t> Candidate;
472 struct CandidateCmp {
473 bool operator()(
const Candidate& c1,
const Candidate& c2)
475 return !SortPolicy::IsBetter(c2.first, c1.first);
480 typedef std::priority_queue<Candidate, std::vector<Candidate>, CandidateCmp>
492#include "lsh_search_impl.hpp"
The LSHSearch class; this class builds a hash on the reference set and uses this hash to compute the ...
size_t BucketSize() const
Get the bucket size of the second hash.
const arma::mat & Offsets() const
Get the offsets 'b' for each of the projections. (One 'b' per column.)
size_t NumProjections() const
Get the number of projections.
const MatType & ReferenceSet() const
Return the reference dataset.
LSHSearch(LSHSearch &&other)
Take ownership of the given LSH model.
LSHSearch()
Create an untrained LSH model.
const std::vector< arma::Col< size_t > > & SecondHashTable() const
Get the second hash table.
LSHSearch(MatType referenceSet, const arma::cube &projections, const double hashWidth=0.0, const size_t secondHashSize=99901, const size_t bucketSize=500)
This function initializes the LSH class.
LSHSearch & operator=(LSHSearch &&other)
Take ownership of the given LSH model.
void Search(const MatType &querySet, const size_t k, arma::Mat< size_t > &resultingNeighbors, arma::mat &distances, const size_t numTablesToSearch=0, const size_t T=0)
Compute the nearest neighbors of the points in the given query set and store the output in the given ...
static double ComputeRecall(const arma::Mat< size_t > &foundNeighbors, const arma::Mat< size_t > &realNeighbors)
Compute the recall (% of neighbors found) given the neighbors returned by LSHSearch::Search and a "gr...
const arma::vec & SecondHashWeights() const
Get the weights of the second hash.
void serialize(Archive &ar, const unsigned int version)
Serialize the LSH model.
const arma::cube & Projections()
Get the projection tables.
LSHSearch(const LSHSearch &other)
Copy the given LSH model.
LSHSearch(MatType referenceSet, const size_t numProj, const size_t numTables, const double hashWidth=0.0, const size_t secondHashSize=99901, const size_t bucketSize=500)
This function initializes the LSH class.
size_t & DistanceEvaluations()
Modify the number of distance evaluations performed.
void Train(MatType referenceSet, const size_t numProj, const size_t numTables, const double hashWidth=0.0, const size_t secondHashSize=99901, const size_t bucketSize=500, const arma::cube &projection=arma::cube())
Train the LSH model on the given dataset.
void Projections(const arma::cube &projTables)
Change the projection tables (this retrains the LSH model).
LSHSearch & operator=(const LSHSearch &other)
Copy the given LSH model.
void Search(const size_t k, arma::Mat< size_t > &resultingNeighbors, arma::mat &distances, const size_t numTablesToSearch=0, size_t T=0)
Compute the nearest neighbors and store the output in the given matrices.
size_t DistanceEvaluations() const
Return the number of distance evaluations performed.
BOOST_TEMPLATE_CLASS_VERSION(template< typename SortPolicy >, mlpack::neighbor::LSHSearch< SortPolicy >, 1)
Set the serialization version of the LSHSearch class.
NearestNS NearestNeighborSort
Linear algebra utility functions, generally performed on matrices or vectors.
The core includes that mlpack expects; standard C++ includes and Armadillo.