Package org.apache.lucene.util.hnsw
Class HnswGraphSearcher
java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphSearcher
Searches an HNSW graph to find nearest neighbors to a query vector. For more background on the
search algorithm, see
HnswGraph
.-
Constructor Summary
ConstructorDescriptionHnswGraphSearcher
(NeighborQueue candidates, BitSet visited) Creates a new graph searcher. -
Method Summary
Modifier and TypeMethodDescriptionstatic 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.searchLevel
(RandomVectorScorer scorer, int topK, int level, int[] eps, HnswGraph graph) Searches for the nearest neighbors of a query vector in a given level.
-
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
-
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
-