HNSW / BIN

HNSW (Hierarchical Navigable Small World Graph) is a graph-based indexing algorithm. It is a method proposed by Yury A. Malkov based on graph indexing, which is an improvement over his previous work. By adopting a hierarchical structure, edges are layered according to feature radius, ensuring that the average degree of each vertex becomes constant across all layers. This reduces the computational complexity of NSW from polylogarithmic to logarithmic complexity.

In such structure the search starts at some enter points (randomly selected or split algorithm) and iteratively traverse the graph. The whole search process is similar to the one to find a location on the earth: we can take earth as the top layer, five continents as the second layer, countries as the third layer, provinces as the fourth layer…If users would like to find Wudaokou area of Haidian District in Beijing, the search can be started from the top layer and traversed as the characteristic radius decreases (first layer: earth -> second layer: fice continents -> third layer: contries -> fourth layer: Haidian District, Beijing). When reaching the zero layer, a more refined search can be conducted in the local area.

Building parameters:

Vectors	Types	Range
M	The number of neighbors each vector has in the graph	[4,96]
ef_construction	The candidate closest neighbors to each top layer when building graph	[8,512]

Table 17 Building Parameter of HNSW

Search parameters:

Vectors	Types	Range
ef_search	The candidate closest neighbors to each top layer when searching targets	[top_k,32768]

Table 18 Search Parameter of HNSW