38 #ifndef __MLPACK_METHODS_NEIGHBOR_SEARCH_LSH_SEARCH_HPP
39 #define __MLPACK_METHODS_NEIGHBOR_SEARCH_LSH_SEARCH_HPP
58 template<
typename SortPolicy = NearestNeighborSort>
112 const size_t numProj,
113 const size_t numTables,
136 void Search(
const size_t k,
137 arma::Mat<size_t>& resultingNeighbors,
138 arma::mat& distances,
139 const size_t numTablesToSearch = 0);
172 arma::uvec& referenceIndices,
173 size_t numTablesToSearch);
182 double BaseCase(
const size_t queryIndex,
const size_t referenceIndex);
197 const size_t neighbor,
const double distance);
254 #include "lsh_search_impl.hpp"
const arma::mat & referenceSet
Reference dataset.
Linear algebra utility functions, generally performed on matrices or vectors.
const arma::mat & querySet
Query dataset (may not be given).
void BuildHash()
This function builds a hash table with two levels of hashing as presented in the paper.
const size_t secondHashSize
The big prime representing the size of the second hash.
metric::SquaredEuclideanDistance metric
Instantiation of the metric.
std::vector< arma::mat > projections
The std::vector containing the projection matrix of each table.
const size_t bucketSize
The bucket size of the second hash.
arma::Col< size_t > bucketContentSize
The number of elements present in each hash bucket; should be secondHashSize.
arma::Mat< size_t > * neighborPtr
The pointer to the nearest neighbor indices.
double BaseCase(const size_t queryIndex, const size_t referenceIndex)
This is a helper function that computes the distance of the query to the neighbor candidates and appr...
The LSHSearch class – This class builds a hash on the reference set and uses this hash to compute th...
const size_t numProj
The number of projections.
std::string ToString() const
arma::mat offsets
The list of the offset 'b' for each of the projection for each table.
The L_p metric for arbitrary integer p, with an option to take the root.
LSHSearch(const arma::mat &referenceSet, const arma::mat &querySet, 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.
void InsertNeighbor(const size_t queryIndex, const size_t pos, const size_t neighbor, const double distance)
This is a helper function that efficiently inserts better neighbor candidates into an existing set of...
const size_t numTables
The number of hash tables.
arma::Mat< size_t > secondHashTable
The final hash table; should be (< secondHashSize) x bucketSize.
void ReturnIndicesFromTable(const size_t queryIndex, arma::uvec &referenceIndices, size_t numTablesToSearch)
This function takes a query and hashes it into each of the hash tables to get keys for the query and ...
arma::vec secondHashWeights
The weights of the second hash.
void Search(const size_t k, arma::Mat< size_t > &resultingNeighbors, arma::mat &distances, const size_t numTablesToSearch=0)
Compute the nearest neighbors and store the output in the given matrices.
double hashWidth
The hash width.
arma::Col< size_t > bucketRowInHashTable
For a particular hash value, points to the row in secondHashTable corresponding to this value...
arma::mat * distancePtr
The pointer to the nearest neighbor distances.