Package org.apache.lucene.util.hnsw
Class HnswGraphSearcher
- java.lang.Object
-
- org.apache.lucene.util.hnsw.HnswGraphSearcher
-
public final class HnswGraphSearcher extends java.lang.Object
Searches an HNSW graph to find nearest neighbors to a query vector. For more background on the search algorithm, seeHnswGraph
.
-
-
Field Summary
Fields Modifier and Type Field Description private NeighborQueue
candidates
Scratch data structures that are used in eachsearchLevel(float[], int, int, int[], org.apache.lucene.index.RandomAccessVectorValues, org.apache.lucene.util.hnsw.HnswGraph)
call.private VectorSimilarityFunction
similarityFunction
private BitSet
visited
-
Constructor Summary
Constructors Constructor Description HnswGraphSearcher(VectorSimilarityFunction similarityFunction, NeighborQueue candidates, BitSet visited)
Creates a new graph searcher.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
clearScratchState()
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.private NeighborQueue
searchLevel(float[] query, int topK, int level, int[] eps, RandomAccessVectorValues vectors, HnswGraph graph, Bits acceptOrds, int visitedLimit)
-
-
-
Field Detail
-
similarityFunction
private final VectorSimilarityFunction similarityFunction
-
candidates
private final NeighborQueue candidates
Scratch data structures that are used in eachsearchLevel(float[], int, int, int[], org.apache.lucene.index.RandomAccessVectorValues, org.apache.lucene.util.hnsw.HnswGraph)
call. These can be expensive to allocate, so they're cleared and reused across calls.
-
visited
private final BitSet visited
-
-
Constructor Detail
-
HnswGraphSearcher
public HnswGraphSearcher(VectorSimilarityFunction similarityFunction, NeighborQueue candidates, BitSet visited)
Creates a new graph searcher.- Parameters:
similarityFunction
- the similarity function to compare vectorscandidates
- max heap that will track the candidate nodes to explorevisited
- 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 java.io.IOException
Searches HNSW graph for the nearest neighbors of a query vector.- Parameters:
query
- search query vectortopK
- the number of nodes to be returnedvectors
- the vector valuessimilarityFunction
- the similarity function to compare vectorsgraph
- 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 priority queue holding the closest neighbors found
- Throws:
java.io.IOException
-
searchLevel
public NeighborQueue searchLevel(float[] query, int topK, int level, int[] eps, RandomAccessVectorValues vectors, HnswGraph graph) throws java.io.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 vectortopK
- the number of nearest to query results to returnlevel
- level to searcheps
- the entry points for search at this level expressed as level 0th ordinalsvectors
- vector valuesgraph
- the graph values- Returns:
- a priority queue holding the closest neighbors found
- Throws:
java.io.IOException
-
searchLevel
private NeighborQueue searchLevel(float[] query, int topK, int level, int[] eps, RandomAccessVectorValues vectors, HnswGraph graph, Bits acceptOrds, int visitedLimit) throws java.io.IOException
- Throws:
java.io.IOException
-
clearScratchState
private void clearScratchState()
-
-