Class HnswGraphSearcher

    • Constructor Detail

      • 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 Detail

      • search

        public static void search​(RandomVectorScorer scorer,
                                  KnnCollector knnCollector,
                                  HnswGraph graph,
                                  Bits acceptOrds)
                           throws java.io.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:
        java.io.IOException
      • search

        public static KnnCollector search​(RandomVectorScorer scorer,
                                          int topK,
                                          OnHeapHnswGraph graph,
                                          Bits acceptOrds,
                                          int visitedLimit)
                                   throws java.io.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:
        java.io.IOException
      • searchLevel

        public HnswGraphBuilder.GraphBuilderKnnCollector searchLevel​(RandomVectorScorer scorer,
                                                                     int topK,
                                                                     int level,
                                                                     int[] eps,
                                                                     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:
        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:
        java.io.IOException
      • findBestEntryPoint

        private int[] findBestEntryPoint​(RandomVectorScorer scorer,
                                         HnswGraph graph,
                                         long visitLimit)
                                  throws java.io.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
        visitLimit - How many vectors are allowed to be visited
        Returns:
        An integer array whose first element is the best entry point, and second is the number of candidates visited. Entry point of `-1` indicates visitation limit exceed
        Throws:
        java.io.IOException - When accessing the vector fails
      • searchLevel

        void searchLevel​(KnnCollector results,
                         RandomVectorScorer scorer,
                         int level,
                         int[] eps,
                         HnswGraph graph,
                         Bits acceptOrds)
                  throws java.io.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:
        java.io.IOException
      • prepareScratchState

        private void prepareScratchState​(int capacity)
      • graphSeek

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

        private static int getGraphSize​(HnswGraph graph)