java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphSearcher<T>
- Type Parameters:
T
- the type of query vector
Searches an HNSW graph to find nearest neighbors to a query vector. For more background on the
search algorithm, see
HnswGraph
.-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final NeighborQueue
Scratch data structures that are used in eachsearchLevel(T, int, int, int[], org.apache.lucene.util.hnsw.RandomAccessVectorValues<T>, org.apache.lucene.util.hnsw.HnswGraph)
call.private final VectorSimilarityFunction
private final VectorEncoding
private BitSet
-
Constructor Summary
ConstructorsConstructorDescriptionHnswGraphSearcher
(VectorEncoding vectorEncoding, VectorSimilarityFunction similarityFunction, NeighborQueue candidates, BitSet visited) Creates a new graph searcher. -
Method Summary
Modifier and TypeMethodDescriptionprivate 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.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)
-
Field Details
-
similarityFunction
-
vectorEncoding
-
candidates
Scratch data structures that are used in eachsearchLevel(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
-
-
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 vectorscandidates
- 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 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 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:
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 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:
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 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:
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
- Throws:
IOException
-
prepareScratchState
private void prepareScratchState(int capacity)
-