Class HnswGraphSearcher

java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphSearcher
Direct Known Subclasses:
HnswConcurrentMergeBuilder.MergeSearcher, HnswGraphSearcher.OnHeapHnswGraphSearcher

public class HnswGraphSearcher 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(NeighborQueue candidates, BitSet visited)
      Creates a new graph searcher.
      Parameters:
      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 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 nodes
      knnCollector - a collector of top knn results to be returned
      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.
      Throws:
      IOException
    • search

      public static KnnCollector search(RandomVectorScorer scorer, int topK, OnHeapHnswGraph graph, Bits acceptOrds, int visitedLimit) throws IOException
      Search OnHeapHnswGraph, this method is thread safe.
      Parameters:
      scorer - the scorer to compare the query with the nodes
      topK - the number of nodes to be returned
      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 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 nodes
      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
      graph - the graph values
      Returns:
      a set of collected vectors holding the nearest neighbors found
      Throws:
      IOException
    • findBestEntryPoint

      private int findBestEntryPoint(RandomVectorScorer scorer, HnswGraph graph, KnnCollector collector) 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 nodes
      graph - the HNSWGraph
      collector - the knn result collector
      Returns:
      the best entry point, `-1` indicates graph entry node not set, or visitation limit exceeded
      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

      void graphSeek(HnswGraph graph, int level, int targetNode) throws IOException
      Seek a specific node in the given graph. The default implementation will just call HnswGraph.seek(int, int)
      Throws:
      IOException - when seeking the graph
    • graphNextNeighbor

      int graphNextNeighbor(HnswGraph graph) throws IOException
      Get the next neighbor from the graph, you must call graphSeek(HnswGraph, int, int) before calling this method. The default implementation will just call HnswGraph.nextNeighbor()
      Returns:
      see HnswGraph.nextNeighbor()
      Throws:
      IOException - when advance neighbors
    • getGraphSize

      private static int getGraphSize(HnswGraph graph)