lsh_search.hpp File Reference

#include <mlpack/prereqs.hpp>
#include <mlpack/core/metrics/lmetric.hpp>
#include <mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp>
#include <queue>
#include "lsh_search_impl.hpp"

Include dependency graph for lsh_search.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	mlpack::neighbor::LSHSearch< SortPolicy, MatType >
	The LSHSearch class; this class builds a hash on the reference set and uses this hash to compute the distance-approximate nearest-neighbors of the given queries. More...

Namespaces
	mlpack
	Linear algebra utility functions, generally performed on matrices or vectors.

Detailed Description

Author

Parikshit Ram

Defines the LSHSearch class, which performs an approximate nearest neighbor search for a queries in a query set over a given dataset using Locality-sensitive hashing with 2-stable distributions.

The details of this method can be found in the following paper:

@inproceedings{datar2004locality,
 title={Locality-sensitive hashing scheme based on p-stable distributions},
 author={Datar, M. and Immorlica, N. and Indyk, P. and Mirrokni, V.S.},
 booktitle=
     {Proceedings of the 12th Annual Symposium on Computational Geometry},
 pages={253--262},
 year={2004},
 organization={ACM}
}

Additionally, the class implements Multiprobe LSH, which improves approximation results during the search for approximate nearest neighbors. The Multiprobe LSH algorithm was presented in the paper:

@inproceedings{Lv2007multiprobe,
 tile={Multi-probe LSH: efficient indexing for high-dimensional similarity
 search},
 author={Lv, Qin and Josephson, William and Wang, Zhe and Charikar, Moses and
 Li, Kai},
 booktitle={Proceedings of the 33rd international conference on Very large
 data bases},
 year={2007},
 pages={950--961}
}

mlpack is free software; you may redistribute it and/or modify it under the terms of the 3-clause BSD license. You should have received a copy of the 3-clause BSD license along with mlpack. If not, see http://www.opensource.org/licenses/BSD-3-Clause for more information.