knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ > Class Template Reference

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

#include <knncolle_hnsw.hpp>

Inheritance diagram for knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ >:

Public Member Functions
	HnswBuilder (DistanceConfig< HnswData_ > distance_config, HnswOptions options)
	HnswBuilder (DistanceConfig< HnswData_ > distance_config)
HnswOptions &	get_options ()
knncolle::Prebuilt< Index_, Data_, Distance_ > *	build_raw (const Matrix_ &data) const
Public Member Functions inherited from knncolle::Builder< typename Index_, typename Data_, typename Distance_, class Matrix_ >
std::shared_ptr< Prebuilt< Index_, Data_, Distance_ > >	build_shared (const Matrix_ &data) const
std::unique_ptr< Prebuilt< Index_, Data_, Distance_ > >	build_unique (const Matrix_ &data) const

Detailed Description

template<typename Index_, typename Data_, typename Distance_, class Matrix_ = knncolle::SimpleMatrix<Index_, Data_>, typename HnswData_ = float>
class knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ >

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.

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

Index_	Integer type for the observation indices.
Data_	Numeric type for the input and query data.
Distance_	Floating point type for the distances.
Matrix_	Class of the input data matrix. This should satisfy the knncolle::Matrix interface.
HnswData_	Type of data in the HNSW index, usually floating-point. This defaults to a float instead of a double to sacrifice some accuracy for performance.

Constructor & Destructor Documentation

HnswBuilder() [1/2]

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = knncolle::SimpleMatrix<Index_, Data_>, typename HnswData_ = float>

knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ >::HnswBuilder ( DistanceConfig< HnswData_ > distance_config, HnswOptions options )

inline

Parameters

distance_config	Configuration for computing distances in the HNSW index, e.g., makeEuclideanDistanceConfig().
options	Further options for HNSW index construction and searching.

HnswBuilder() [2/2]

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = knncolle::SimpleMatrix<Index_, Data_>, typename HnswData_ = float>

knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ >::HnswBuilder ( DistanceConfig< HnswData_ > distance_config )

inline

Overload that uses the default Options.

Parameters

distance_config

Configuration for computing distances in the HNSW index, e.g., makeEuclideanDistanceConfig().

Member Function Documentation

build_raw()

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = knncolle::SimpleMatrix<Index_, Data_>, typename HnswData_ = float>

knncolle::Prebuilt< Index_, Data_, Distance_ > * knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ >::build_raw ( const Matrix_ & data ) const

inlinevirtual

Creates a HnswPrebuilt instance.

Implements knncolle::Builder< typename Index_, typename Data_, typename Distance_, class Matrix_ >.

get_options()

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = knncolle::SimpleMatrix<Index_, Data_>, typename HnswData_ = float>

HnswOptions & knncolle_hnsw::HnswBuilder< Index_, Data_, Distance_, Matrix_, HnswData_ >::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