Krotos Modules 3
Loading...
Searching...
No Matches
Classes | Public Member Functions | Public Attributes | Static Public Attributes | List of all members
hnswlib::HierarchicalNSW< dist_t > Class Template Reference

#include <hnswalg.h>

Inheritance diagram for hnswlib::HierarchicalNSW< dist_t >:
hnswlib::AlgorithmInterface< dist_t >

Classes

struct  CompareByFirst
 

Public Member Functions

 HierarchicalNSW (SpaceInterface< dist_t > *)
 
 HierarchicalNSW (SpaceInterface< dist_t > *s, const std::string &location, bool nmslib=false, size_t max_elements=0)
 
 HierarchicalNSW (SpaceInterface< dist_t > *s, size_t max_elements, size_t M=16, size_t ef_construction=200, size_t random_seed=100)
 
 ~HierarchicalNSW ()
 
labeltype getExternalLabel (tableint internal_id) const
 
void setExternalLabel (tableint internal_id, labeltype label) const
 
labeltype * getExternalLabeLp (tableint internal_id) const
 
char * getDataByInternalId (tableint internal_id) const
 
int getRandomLevel (double reverse_size)
 
std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > searchBaseLayer (tableint ep_id, const void *data_point, int layer)
 
template<bool has_deletions, bool collect_metrics = false>
std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > searchBaseLayerST (tableint ep_id, const void *data_point, size_t ef) const
 
void getNeighborsByHeuristic2 (std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > &top_candidates, const size_t M)
 
linklistsizeint * get_linklist0 (tableint internal_id) const
 
linklistsizeint * get_linklist (tableint internal_id, int level) const
 
linklistsizeint * get_linklist_at_level (tableint internal_id, int level) const
 
tableint mutuallyConnectNewElement (const void *, tableint cur_c, std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > &top_candidates, int level, bool isUpdate)
 
void setEf (size_t ef)
 
std::priority_queue< std::pair< dist_t, tableint > > searchKnnInternal (void *query_data, int k)
 
void resizeIndex (size_t new_max_elements)
 
void saveIndex (const std::string &location)
 
void loadIndex (const std::string &location, SpaceInterface< dist_t > *s, bool, size_t max_elements_i=0)
 
template<typename data_t >
std::vector< data_t > getDataByLabel (labeltype label) const
 
void markDelete (labeltype label)
 
void markDeletedInternal (tableint internalId)
 
void unmarkDelete (labeltype label)
 
void unmarkDeletedInternal (tableint internalId)
 
bool isMarkedDeleted (tableint internalId) const
 
unsigned short int getListCount (linklistsizeint *ptr) const
 
void setListCount (linklistsizeint *ptr, unsigned short int size) const
 
void addPoint (const void *data_point, labeltype label)
 
void updatePoint (const void *dataPoint, tableint internalId, float updateNeighborProbability)
 
void repairConnectionsForUpdate (const void *dataPoint, tableint entryPointInternalId, tableint dataPointInternalId, int dataPointLevel, int maxLevel)
 
std::vector< tableint > getConnectionsWithLock (tableint internalId, int level)
 
tableint addPoint (const void *data_point, labeltype label, int level)
 
std::priority_queue< std::pair< dist_t, labeltype > > searchKnn (const void *query_data, size_t k) const
 
void checkIntegrity ()
 
- Public Member Functions inherited from hnswlib::AlgorithmInterface< dist_t >
virtual std::vector< std::pair< dist_t, labeltype > > searchKnnCloserFirst (const void *query_data, size_t k) const
 
virtual ~AlgorithmInterface ()
 

Public Attributes

size_t max_elements_
 
size_t cur_element_count
 
size_t size_data_per_element_
 
size_t size_links_per_element_
 
size_t num_deleted_
 
size_t M_
 
size_t maxM_
 
size_t maxM0_
 
size_t ef_construction_
 
double mult_
 
double revSize_
 
int maxlevel_
 
VisitedListPool * visited_list_pool_
 
std::mutex cur_element_count_guard_
 
std::vector< std::mutex > link_list_locks_
 
std::vector< std::mutex > link_list_update_locks_
 
tableint enterpoint_node_
 
size_t size_links_level0_
 
size_t offsetData_
 
size_t offsetLevel0_
 
char * data_level0_memory_
 
char ** linkLists_
 
std::vector< int > element_levels_
 
size_t data_size_
 
size_t label_offset_
 
DISTFUNC< dist_t > fstdistfunc_
 
void * dist_func_param_
 
std::unordered_map< labeltype, tableint > label_lookup_
 
std::default_random_engine level_generator_
 
std::default_random_engine update_probability_generator_
 
std::atomic< long > metric_distance_computations
 
std::atomic< long > metric_hops
 
std::mutex global
 
size_t ef_
 

Static Public Attributes

static const tableint max_update_element_locks = 65536
 
static const unsigned char DELETE_MARK = 0x01
 

Constructor & Destructor Documentation

◆ HierarchicalNSW() [1/3]

template<typename dist_t >
hnswlib::HierarchicalNSW< dist_t >::HierarchicalNSW ( SpaceInterface< dist_t > * )
inline

◆ HierarchicalNSW() [2/3]

template<typename dist_t >
hnswlib::HierarchicalNSW< dist_t >::HierarchicalNSW ( SpaceInterface< dist_t > * s,
const std::string & location,
bool nmslib = false,
size_t max_elements = 0 )
inline

◆ HierarchicalNSW() [3/3]

template<typename dist_t >
hnswlib::HierarchicalNSW< dist_t >::HierarchicalNSW ( SpaceInterface< dist_t > * s,
size_t max_elements,
size_t M = 16,
size_t ef_construction = 200,
size_t random_seed = 100 )
inline

◆ ~HierarchicalNSW()

template<typename dist_t >
hnswlib::HierarchicalNSW< dist_t >::~HierarchicalNSW ( )
inline

Member Function Documentation

◆ addPoint() [1/2]

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::addPoint ( const void * data_point,
labeltype label )
inlinevirtual

Implements hnswlib::AlgorithmInterface< dist_t >.

◆ addPoint() [2/2]

template<typename dist_t >
tableint hnswlib::HierarchicalNSW< dist_t >::addPoint ( const void * data_point,
labeltype label,
int level )
inline

◆ checkIntegrity()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::checkIntegrity ( )
inline

◆ get_linklist()

template<typename dist_t >
linklistsizeint * hnswlib::HierarchicalNSW< dist_t >::get_linklist ( tableint internal_id,
int level ) const
inline

◆ get_linklist0()

template<typename dist_t >
linklistsizeint * hnswlib::HierarchicalNSW< dist_t >::get_linklist0 ( tableint internal_id) const
inline

◆ get_linklist_at_level()

template<typename dist_t >
linklistsizeint * hnswlib::HierarchicalNSW< dist_t >::get_linklist_at_level ( tableint internal_id,
int level ) const
inline

◆ getConnectionsWithLock()

template<typename dist_t >
std::vector< tableint > hnswlib::HierarchicalNSW< dist_t >::getConnectionsWithLock ( tableint internalId,
int level )
inline

◆ getDataByInternalId()

template<typename dist_t >
char * hnswlib::HierarchicalNSW< dist_t >::getDataByInternalId ( tableint internal_id) const
inline

◆ getDataByLabel()

template<typename dist_t >
template<typename data_t >
std::vector< data_t > hnswlib::HierarchicalNSW< dist_t >::getDataByLabel ( labeltype label) const
inline

◆ getExternalLabel()

template<typename dist_t >
labeltype hnswlib::HierarchicalNSW< dist_t >::getExternalLabel ( tableint internal_id) const
inline

◆ getExternalLabeLp()

template<typename dist_t >
labeltype * hnswlib::HierarchicalNSW< dist_t >::getExternalLabeLp ( tableint internal_id) const
inline

◆ getListCount()

template<typename dist_t >
unsigned short int hnswlib::HierarchicalNSW< dist_t >::getListCount ( linklistsizeint * ptr) const
inline

◆ getNeighborsByHeuristic2()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::getNeighborsByHeuristic2 ( std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > & top_candidates,
const size_t M )
inline

◆ getRandomLevel()

template<typename dist_t >
int hnswlib::HierarchicalNSW< dist_t >::getRandomLevel ( double reverse_size)
inline

◆ isMarkedDeleted()

template<typename dist_t >
bool hnswlib::HierarchicalNSW< dist_t >::isMarkedDeleted ( tableint internalId) const
inline

Checks the first 8 bits of the memory to see if the element is marked deleted.

Parameters
internalId
Returns

◆ loadIndex()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::loadIndex ( const std::string & location,
SpaceInterface< dist_t > * s,
bool ,
size_t max_elements_i = 0 )
inline

Optional - check if index is ok:

Optional check end

◆ markDelete()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::markDelete ( labeltype label)
inline

Marks an element with the given label deleted, does NOT really change the current graph.

Parameters
label

◆ markDeletedInternal()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::markDeletedInternal ( tableint internalId)
inline

Uses the first 8 bits of the memory for the linked list to store the mark, whereas maxM0_ has to be limited to the lower 24 bits, however, still large enough in almost all cases.

Parameters
internalId

◆ mutuallyConnectNewElement()

template<typename dist_t >
tableint hnswlib::HierarchicalNSW< dist_t >::mutuallyConnectNewElement ( const void * ,
tableint cur_c,
std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > & top_candidates,
int level,
bool isUpdate )
inline

◆ repairConnectionsForUpdate()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::repairConnectionsForUpdate ( const void * dataPoint,
tableint entryPointInternalId,
tableint dataPointInternalId,
int dataPointLevel,
int maxLevel )
inline

◆ resizeIndex()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::resizeIndex ( size_t new_max_elements)
inline

◆ saveIndex()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::saveIndex ( const std::string & location)
inlinevirtual

Implements hnswlib::AlgorithmInterface< dist_t >.

◆ searchBaseLayer()

template<typename dist_t >
std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > hnswlib::HierarchicalNSW< dist_t >::searchBaseLayer ( tableint ep_id,
const void * data_point,
int layer )
inline

◆ searchBaseLayerST()

template<typename dist_t >
template<bool has_deletions, bool collect_metrics = false>
std::priority_queue< std::pair< dist_t, tableint >, std::vector< std::pair< dist_t, tableint > >, CompareByFirst > hnswlib::HierarchicalNSW< dist_t >::searchBaseLayerST ( tableint ep_id,
const void * data_point,
size_t ef ) const
inline

◆ searchKnn()

template<typename dist_t >
std::priority_queue< std::pair< dist_t, labeltype > > hnswlib::HierarchicalNSW< dist_t >::searchKnn ( const void * query_data,
size_t k ) const
inlinevirtual

Implements hnswlib::AlgorithmInterface< dist_t >.

◆ searchKnnInternal()

template<typename dist_t >
std::priority_queue< std::pair< dist_t, tableint > > hnswlib::HierarchicalNSW< dist_t >::searchKnnInternal ( void * query_data,
int k )
inline

◆ setEf()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::setEf ( size_t ef)
inline

◆ setExternalLabel()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::setExternalLabel ( tableint internal_id,
labeltype label ) const
inline

◆ setListCount()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::setListCount ( linklistsizeint * ptr,
unsigned short int size ) const
inline

◆ unmarkDelete()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::unmarkDelete ( labeltype label)
inline

Remove the deleted mark of the node, does NOT really change the current graph.

Parameters
label

◆ unmarkDeletedInternal()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::unmarkDeletedInternal ( tableint internalId)
inline

Remove the deleted mark of the node.

Parameters
internalId

◆ updatePoint()

template<typename dist_t >
void hnswlib::HierarchicalNSW< dist_t >::updatePoint ( const void * dataPoint,
tableint internalId,
float updateNeighborProbability )
inline

Member Data Documentation

◆ cur_element_count

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::cur_element_count

◆ cur_element_count_guard_

template<typename dist_t >
std::mutex hnswlib::HierarchicalNSW< dist_t >::cur_element_count_guard_

◆ data_level0_memory_

template<typename dist_t >
char* hnswlib::HierarchicalNSW< dist_t >::data_level0_memory_

◆ data_size_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::data_size_

◆ DELETE_MARK

template<typename dist_t >
const unsigned char hnswlib::HierarchicalNSW< dist_t >::DELETE_MARK = 0x01
static

◆ dist_func_param_

template<typename dist_t >
void* hnswlib::HierarchicalNSW< dist_t >::dist_func_param_

◆ ef_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::ef_

◆ ef_construction_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::ef_construction_

◆ element_levels_

template<typename dist_t >
std::vector<int> hnswlib::HierarchicalNSW< dist_t >::element_levels_

◆ enterpoint_node_

template<typename dist_t >
tableint hnswlib::HierarchicalNSW< dist_t >::enterpoint_node_

◆ fstdistfunc_

template<typename dist_t >
DISTFUNC<dist_t> hnswlib::HierarchicalNSW< dist_t >::fstdistfunc_

◆ global

template<typename dist_t >
std::mutex hnswlib::HierarchicalNSW< dist_t >::global

◆ label_lookup_

template<typename dist_t >
std::unordered_map<labeltype, tableint> hnswlib::HierarchicalNSW< dist_t >::label_lookup_

◆ label_offset_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::label_offset_

◆ level_generator_

template<typename dist_t >
std::default_random_engine hnswlib::HierarchicalNSW< dist_t >::level_generator_

◆ link_list_locks_

template<typename dist_t >
std::vector<std::mutex> hnswlib::HierarchicalNSW< dist_t >::link_list_locks_

◆ link_list_update_locks_

template<typename dist_t >
std::vector<std::mutex> hnswlib::HierarchicalNSW< dist_t >::link_list_update_locks_

◆ linkLists_

template<typename dist_t >
char** hnswlib::HierarchicalNSW< dist_t >::linkLists_

◆ M_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::M_

◆ max_elements_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::max_elements_

◆ max_update_element_locks

template<typename dist_t >
const tableint hnswlib::HierarchicalNSW< dist_t >::max_update_element_locks = 65536
static

◆ maxlevel_

template<typename dist_t >
int hnswlib::HierarchicalNSW< dist_t >::maxlevel_

◆ maxM0_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::maxM0_

◆ maxM_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::maxM_

◆ metric_distance_computations

template<typename dist_t >
std::atomic<long> hnswlib::HierarchicalNSW< dist_t >::metric_distance_computations
mutable

◆ metric_hops

template<typename dist_t >
std::atomic<long> hnswlib::HierarchicalNSW< dist_t >::metric_hops
mutable

◆ mult_

template<typename dist_t >
double hnswlib::HierarchicalNSW< dist_t >::mult_

◆ num_deleted_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::num_deleted_

◆ offsetData_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::offsetData_

◆ offsetLevel0_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::offsetLevel0_

◆ revSize_

template<typename dist_t >
double hnswlib::HierarchicalNSW< dist_t >::revSize_

◆ size_data_per_element_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::size_data_per_element_

◆ size_links_level0_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::size_links_level0_

◆ size_links_per_element_

template<typename dist_t >
size_t hnswlib::HierarchicalNSW< dist_t >::size_links_per_element_

◆ update_probability_generator_

template<typename dist_t >
std::default_random_engine hnswlib::HierarchicalNSW< dist_t >::update_probability_generator_

◆ visited_list_pool_

template<typename dist_t >
VisitedListPool* hnswlib::HierarchicalNSW< dist_t >::visited_list_pool_
The documentation for this class was generated from the following file: