Module org.apache.lucene.core

Package org.apache.lucene.util.hnsw

Class HnswGraphSearcher

java.lang.Object

org.apache.lucene.util.hnsw.HnswGraphSearcher

Direct Known Subclasses:

HnswConcurrentMergeBuilder.MergeSearcher, HnswGraphSearcher.OnHeapHnswGraphSearcher

public 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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	HnswGraphSearcher.OnHeapHnswGraphSearcher	This class allows OnHeapHnswGraph to be searched in a thread-safe manner by avoiding the unsafe methods (seek and nextNeighbor, which maintain state in the graph object) and instead maintaining the state in the searcher object.

Field Summary

Fields

Modifier and Type	Field	Description
private final NeighborQueue	candidates	Scratch data structures that are used in each searchLevel(org.apache.lucene.util.hnsw.RandomVectorScorer, int, int, int[], org.apache.lucene.util.hnsw.HnswGraph) call.
private BitSet	visited

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private int	findBestEntryPoint(RandomVectorScorer scorer, HnswGraph graph, KnnCollector collector)	Function to find the best entry point from which to search the zeroth graph layer.
private static int	getGraphSize(HnswGraph graph)
(package private) int	graphNextNeighbor(HnswGraph graph)	Get the next neighbor from the graph, you must call graphSeek(HnswGraph, int, int) before calling this method.
(package private) void	graphSeek(HnswGraph graph, int level, int targetNode)	Seek a specific node in the given graph.
private void	prepareScratchState(int capacity)
static KnnCollector	search(RandomVectorScorer scorer, int topK, OnHeapHnswGraph graph, Bits acceptOrds, int visitedLimit)	Search OnHeapHnswGraph, this method is thread safe.
static void	search(RandomVectorScorer scorer, KnnCollector knnCollector, HnswGraph graph, Bits acceptOrds)	Searches HNSW graph for the nearest neighbors of a query vector.
private static void	search(RandomVectorScorer scorer, KnnCollector knnCollector, HnswGraph graph, HnswGraphSearcher graphSearcher, Bits acceptOrds)
(package private) void	searchLevel(KnnCollector results, RandomVectorScorer scorer, int level, int[] eps, HnswGraph graph, Bits acceptOrds)	Add the closest neighbors found to a priority queue (heap).
HnswGraphBuilder.GraphBuilderKnnCollector	searchLevel(RandomVectorScorer scorer, int topK, int level, int[] eps, 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

Field Details

candidates

private final NeighborQueue candidates

Scratch data structures that are used in each searchLevel(org.apache.lucene.util.hnsw.RandomVectorScorer, int, int, int[], 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(NeighborQueue candidates,
 BitSet visited)

Creates a new graph searcher.

Parameters:

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 void search(RandomVectorScorer scorer,
 KnnCollector knnCollector,
 HnswGraph graph,
 Bits acceptOrds)
                   throws IOException

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

Parameters:

scorer - the scorer to compare the query with the nodes

knnCollector - a collector of top knn results to be returned

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.

Throws:

IOException

search

public static KnnCollector search(RandomVectorScorer scorer,
 int topK,
 OnHeapHnswGraph graph,
 Bits acceptOrds,
 int visitedLimit)
                           throws IOException

Search OnHeapHnswGraph, this method is thread safe.

Parameters:

scorer - the scorer to compare the query with the nodes

topK - the number of nodes to be returned

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 set of collected vectors holding the nearest neighbors found

Throws:

IOException

search

private static void search(RandomVectorScorer scorer,
 KnnCollector knnCollector,
 HnswGraph graph,
 HnswGraphSearcher graphSearcher,
 Bits acceptOrds)
                    throws IOException

Throws:

IOException

searchLevel

public HnswGraphBuilder.GraphBuilderKnnCollector searchLevel(RandomVectorScorer scorer,
 int topK,
 int level,
 int[] eps,
 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:

scorer - the scorer to compare the query with the nodes

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

graph - the graph values

Returns:

a set of collected vectors holding the nearest neighbors found

Throws:

IOException

findBestEntryPoint

private int findBestEntryPoint(RandomVectorScorer scorer,
 HnswGraph graph,
 KnnCollector collector)
                        throws IOException

Function to find the best entry point from which to search the zeroth graph layer.

Parameters:

scorer - the scorer to compare the query with the nodes

graph - the HNSWGraph

collector - the knn result collector

Returns:

the best entry point, `-1` indicates graph entry node not set, or visitation limit exceeded

Throws:

IOException - When accessing the vector fails

searchLevel

void searchLevel(KnnCollector results,
 RandomVectorScorer scorer,
 int level,
 int[] eps,
 HnswGraph graph,
 Bits acceptOrds)
          throws IOException

Add the closest neighbors found to a priority queue (heap). These are returned in REVERSE proximity order -- the most distant neighbor of the topK found, i.e. the one with the lowest score/comparison value, will be at the top of the heap, while the closest neighbor will be the last to be popped.

Throws:

IOException

prepareScratchState

private void prepareScratchState(int capacity)

graphSeek

void graphSeek(HnswGraph graph,
 int level,
 int targetNode)
        throws IOException

Seek a specific node in the given graph. The default implementation will just call HnswGraph.seek(int, int)

Throws:

IOException - when seeking the graph

graphNextNeighbor

int graphNextNeighbor(HnswGraph graph)
               throws IOException

Get the next neighbor from the graph, you must call graphSeek(HnswGraph, int, int) before calling this method. The default implementation will just call HnswGraph.nextNeighbor()

Returns:

see HnswGraph.nextNeighbor()

Throws:

IOException - when advance neighbors

getGraphSize

private static int getGraphSize(HnswGraph graph)