Package org.apache.lucene.util.hnsw

Class HnswGraphSearcher

java.lang.Object

org.apache.lucene.util.hnsw.HnswGraphSearcher

public final class HnswGraphSearcher
extends Object

Searches an HNSW graph to find nearest neighbors to a query vector. For more background on the search algorithm, see HnswGraph.

Constructor Summary

Constructors

Constructor	Description
HnswGraphSearcher(VectorSimilarityFunction similarityFunction, NeighborQueue candidates, BitSet visited)	Creates a new graph searcher.

Method Summary

Modifier and Type	Method	Description
static NeighborQueue	search(float[] query, int topK, RandomAccessVectorValues vectors, VectorSimilarityFunction similarityFunction, HnswGraph graph, Bits acceptOrds, int visitedLimit)	Searches HNSW graph for the nearest neighbors of a query vector.
NeighborQueue	searchLevel(float[] query, int topK, int level, int[] eps, RandomAccessVectorValues vectors, HnswGraph graph)	Searches for the nearest neighbors of a query vector in a given level.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HnswGraphSearcher

public HnswGraphSearcher(VectorSimilarityFunction similarityFunction,
                         NeighborQueue candidates,
                         BitSet visited)

Creates a new graph searcher.

Parameters:

similarityFunction - the similarity function to compare vectors

candidates - max heap that will track the candidate nodes to explore

visited - bit set that will track nodes that have already been visited

Method Detail

search

public static NeighborQueue search(float[] query,
                                   int topK,
                                   RandomAccessVectorValues vectors,
                                   VectorSimilarityFunction similarityFunction,
                                   HnswGraph graph,
                                   Bits acceptOrds,
                                   int visitedLimit)
                            throws IOException

Searches HNSW graph for the nearest neighbors of a query vector.

Parameters:

query - search query vector

topK - the number of nodes to be returned

vectors - the vector values

similarityFunction - the similarity function to compare vectors

graph - the graph values. May represent the entire graph, or a level in a hierarchical graph.

acceptOrds - Bits that represents the allowed document ordinals to match, or null if they are all allowed to match.

visitedLimit - the maximum number of nodes that the search is allowed to visit

Returns:

a priority queue holding the closest neighbors found

Throws:

IOException

searchLevel

public NeighborQueue searchLevel(float[] query,
                                 int topK,
                                 int level,
                                 int[] eps,
                                 RandomAccessVectorValues vectors,
                                 HnswGraph graph)
                          throws IOException

Searches for the nearest neighbors of a query vector in a given level.

If the search stops early because it reaches the visited nodes limit, then the results will be marked incomplete through NeighborQueue.incomplete().

Parameters:

query - search query vector

topK - the number of nearest to query results to return

level - level to search

eps - the entry points for search at this level expressed as level 0th ordinals

vectors - vector values

graph - the graph values

Returns:

a priority queue holding the closest neighbors found

Throws:

IOException