Perform an approximate nearest neighbor search with HNSW. More...

#include <knncolle_hnsw.hpp>

Inheritance diagram for knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ >:

Public Types
typedef HnswOptions< typename Matrix_::dimension_type, InternalData_ >	Options

Public Member Functions
	HnswBuilder (Options options)

	HnswBuilder ()=default

Options &	get_options ()

knncolle::Prebuilt< typename Matrix_::dimension_type, typename Matrix_::index_type, Float_ > *	build_raw (const Matrix_ &data) const

Public Member Functions inherited from knncolle::Builder< class Matrix_, typename Float_ >
std::shared_ptr< Prebuilt< typename Matrix_::dimension_type, typename Matrix_::index_type, Float_ > >	build_shared (const Matrix_ &data) const

std::unique_ptr< Prebuilt< typename Matrix_::dimension_type, typename Matrix_::index_type, Float_ > >	build_unique (const Matrix_ &data) const

Detailed Description

template<class Matrix_ = knncolle::SimpleMatrix<int, int, double>, typename Float_ = double, typename InternalData_ = float>
class knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ >

Perform an approximate nearest neighbor search with HNSW.

In the HNSW algorithm (Malkov and Yashunin, 2016), each point is a node in a "nagivable small world" graph. The nearest neighbor search proceeds by starting at a node and walking through the graph to obtain closer neighbors to a given query point. Nagivable small world graphs are used to maintain connectivity across the data set by creating links between distant points. This speeds up the search by ensuring that the algorithm does not need to take many small steps to move from one cluster to another. The HNSW algorithm extends this idea by using a hierarchy of such graphs containing links of different lengths, which avoids wasting time on small steps in the early stages of the search where the current node position is far from the query.

The build_raw() method will create an instance of the HnswPrebuilt class.

See also: Malkov YA, Yashunin DA (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv. https://arxiv.org/abs/1603.09320

Template Parameters

Matrix_	Matrix-like object satisfying the `knncolle::MockMatrix` interface.
Float_	Floating point type for the query data and output distances.
InternalData_	Floating point type for the internal data in HNSW index. This defaults to a `float` instead of a `double` to sacrifice some accuracy for performance.