Class HnswGraphSearcher<T>

java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphSearcher<T>
Type Parameters:
T - the type of query vector

public class HnswGraphSearcher<T> extends Object
Searches an HNSW graph to find nearest neighbors to a query vector. For more background on the search algorithm, see HnswGraph.
  • Field Details

  • 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 vectors
      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 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 vector
      topK - the number of nodes to be returned
      vectors - the vector values
      similarityFunction - the similarity function to compare vectors
      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 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 vector
      topK - the number of nodes to be returned
      vectors - the vector values
      similarityFunction - the similarity function to compare vectors
      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 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 vector
      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
      vectors - vector values
      graph - 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

      private float compare(T query, RandomAccessVectorValues<T> vectors, int ord) throws IOException
      Throws:
      IOException
    • prepareScratchState

      private void prepareScratchState(int capacity)