Module org.apache.lucene.core

Package org.apache.lucene.util.hnsw

Class HnswGraphSearcher<T>

java.lang.Object

org.apache.lucene.util.hnsw.HnswGraphSearcher<T>

Type Parameters:

T - the type of query vector

public class HnswGraphSearcher<T>
extends Object

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

Field Summary

Fields

Modifier and Type	Field	Description
private final NeighborQueue	candidates	Scratch data structures that are used in each searchLevel(T, int, int, int[], org.apache.lucene.util.hnsw.RandomAccessVectorValues<T>, org.apache.lucene.util.hnsw.HnswGraph) call.
private final VectorSimilarityFunction	similarityFunction
private final VectorEncoding	vectorEncoding
private BitSet	visited

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private float	compare(T query, RandomAccessVectorValues<T> vectors, int ord)
private void	prepareScratchState(int capacity)
static NeighborQueue	search(byte[] query, int topK, RandomAccessVectorValues<byte[]> vectors, VectorEncoding vectorEncoding, VectorSimilarityFunction similarityFunction, HnswGraph graph, Bits acceptOrds, int visitedLimit)	Searches HNSW graph for the nearest neighbors of a query vector.
static NeighborQueue	search(float[] query, int topK, RandomAccessVectorValues<float[]> vectors, VectorEncoding vectorEncoding, VectorSimilarityFunction similarityFunction, HnswGraph graph, Bits acceptOrds, int visitedLimit)	Searches HNSW graph for the nearest neighbors of a query vector.
NeighborQueue	searchLevel(T query, int topK, int level, int[] eps, RandomAccessVectorValues<T> vectors, HnswGraph graph)	Searches for the nearest neighbors of a query vector in a given level.
private NeighborQueue	searchLevel(T query, int topK, int level, int[] eps, RandomAccessVectorValues<T> vectors, HnswGraph graph, Bits acceptOrds, int visitedLimit)

Methods inherited from class java.lang.Object

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

Field Details

similarityFunction

private final VectorSimilarityFunction similarityFunction

vectorEncoding

private final VectorEncoding vectorEncoding

candidates

private final NeighborQueue candidates

Scratch data structures that are used in each searchLevel(T, int, int, int[], org.apache.lucene.util.hnsw.RandomAccessVectorValues<T>, org.apache.lucene.util.hnsw.HnswGraph) call. These can be expensive to allocate, so they're cleared and reused across calls.

visited

private BitSet visited

Constructor Details

HnswGraphSearcher

public HnswGraphSearcher(VectorEncoding vectorEncoding,
 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 Details

search

public static NeighborQueue search(float[] query,
 int topK,
 RandomAccessVectorValues<float[]> vectors,
 VectorEncoding vectorEncoding,
 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

search

public static NeighborQueue search(byte[] query,
 int topK,
 RandomAccessVectorValues<byte[]> vectors,
 VectorEncoding vectorEncoding,
 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(T query,
 int topK,
 int level,
 int[] eps,
 RandomAccessVectorValues<T> 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

searchLevel

private NeighborQueue searchLevel(T query,
 int topK,
 int level,
 int[] eps,
 RandomAccessVectorValues<T> vectors,
 HnswGraph graph,
 Bits acceptOrds,
 int visitedLimit)
                           throws IOException

Throws:

IOException

compare

private float compare(T query,
 RandomAccessVectorValues<T> vectors,
 int ord)
               throws IOException

Throws:

IOException

prepareScratchState

private void prepareScratchState(int capacity)