knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ > Class Template Reference

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.

Member Typedef Documentation

Options

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

typedef HnswOptions<typename Matrix_::dimension_type, InternalData_> knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ >::Options

Convenient name for the HnswOptions class that ensures consistent template parametrization.

Constructor & Destructor Documentation

HnswBuilder() [1/2]

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

knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ >::HnswBuilder ( Options  options )

inline

Parameters

options

Further options for HNSW index construction and searching.

HnswBuilder() [2/2]

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

knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ >::HnswBuilder ( )

default

Default constructor.

Member Function Documentation

build_raw()

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

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

inlinevirtual

Implements knncolle::Builder< class Matrix_, typename Float_ >.

get_options()

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

Options & knncolle_hnsw::HnswBuilder< Matrix_, Float_, InternalData_ >::get_options ( )

inline

Returns

Options for HNSW, to be modified prior to calling build_raw() and friends.

---

The documentation for this class was generated from the following file:

• knncolle_hnsw/knncolle_hnsw.hpp