java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphSearcher
- Direct Known Subclasses:
HnswConcurrentMergeBuilder.MergeSearcher
,HnswGraphSearcher.OnHeapHnswGraphSearcher
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 ClassesModifier and TypeClassDescriptionprivate static class
This class allowsOnHeapHnswGraph
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
FieldsModifier and TypeFieldDescriptionprivate final NeighborQueue
Scratch data structures that are used in eachsearchLevel(org.apache.lucene.util.hnsw.RandomVectorScorer, int, int, int[], org.apache.lucene.util.hnsw.HnswGraph)
call.private BitSet
-
Constructor Summary
ConstructorsConstructorDescriptionHnswGraphSearcher
(NeighborQueue candidates, BitSet visited) Creates a new graph searcher. -
Method Summary
Modifier and TypeMethodDescriptionprivate int[]
findBestEntryPoint
(RandomVectorScorer scorer, HnswGraph graph, long visitLimit) 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 callgraphSeek(HnswGraph, int, int)
before calling this method.(package private) void
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) SearchOnHeapHnswGraph
, 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).searchLevel
(RandomVectorScorer scorer, int topK, int level, int[] eps, HnswGraph graph) Searches for the nearest neighbors of a query vector in a given level.
-
Field Details
-
candidates
Scratch data structures that are used in eachsearchLevel(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
-
-
Constructor Details
-
HnswGraphSearcher
Creates a new graph searcher.- Parameters:
candidates
- max heap that will track the candidate nodes to explorevisited
- 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 nodesknnCollector
- a collector of top knn results to be returnedgraph
- 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, ornull
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 SearchOnHeapHnswGraph
, this method is thread safe.- Parameters:
scorer
- the scorer to compare the query with the nodestopK
- the number of nodes to be returnedgraph
- 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, ornull
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 nodestopK
- the number of nearest to query results to returnlevel
- level to searcheps
- the entry points for search at this level expressed as level 0th ordinalsgraph
- the graph values- Returns:
- a set of collected vectors holding the nearest neighbors found
- Throws:
IOException
-
findBestEntryPoint
private int[] findBestEntryPoint(RandomVectorScorer scorer, HnswGraph graph, long visitLimit) 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 nodesgraph
- the HNSWGraphvisitLimit
- How many vectors are allowed to be visited- Returns:
- An integer array whose first element is the best entry point, and second is the number of candidates visited. Entry point of `-1` indicates visitation limit exceed
- 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
Seek a specific node in the given graph. The default implementation will just callHnswGraph.seek(int, int)
- Throws:
IOException
- when seeking the graph
-
graphNextNeighbor
Get the next neighbor from the graph, you must callgraphSeek(HnswGraph, int, int)
before calling this method. The default implementation will just callHnswGraph.nextNeighbor()
- Returns:
- see
HnswGraph.nextNeighbor()
- Throws:
IOException
- when advance neighbors
-
getGraphSize
-