Class HnswGraphBuilder

    • Constructor Detail

      • HnswGraphBuilder

        protected HnswGraphBuilder​(RandomVectorScorerSupplier scorerSupplier,
                                   int M,
                                   int beamWidth,
                                   long seed,
                                   int graphSize)
                            throws java.io.IOException
        Reads all the vectors from vector values, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.
        Parameters:
        scorerSupplier - a supplier to create vector scorer from ordinals.
        M - – graph fanout parameter used to calculate the maximum number of connections a node can have – M on upper layers, and M * 2 on the lowest level.
        beamWidth - the size of the beam search to use when finding nearest neighbors.
        seed - the seed for a random number generator used during graph construction. Provide this to ensure repeatable construction.
        graphSize - size of graph, if unknown, pass in -1
        Throws:
        java.io.IOException
      • HnswGraphBuilder

        protected HnswGraphBuilder​(RandomVectorScorerSupplier scorerSupplier,
                                   int M,
                                   int beamWidth,
                                   long seed,
                                   OnHeapHnswGraph hnsw)
                            throws java.io.IOException
        Throws:
        java.io.IOException
      • HnswGraphBuilder

        protected HnswGraphBuilder​(RandomVectorScorerSupplier scorerSupplier,
                                   int M,
                                   int beamWidth,
                                   long seed,
                                   OnHeapHnswGraph hnsw,
                                   HnswGraphSearcher graphSearcher)
                            throws java.io.IOException
        Reads all the vectors from vector values, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.
        Parameters:
        scorerSupplier - a supplier to create vector scorer from ordinals.
        M - – graph fanout parameter used to calculate the maximum number of connections a node can have – M on upper layers, and M * 2 on the lowest level.
        beamWidth - the size of the beam search to use when finding nearest neighbors.
        seed - the seed for a random number generator used during graph construction. Provide this to ensure repeatable construction.
        hnsw - the graph to build, can be previously initialized
        Throws:
        java.io.IOException
    • Method Detail

      • build

        public OnHeapHnswGraph build​(int maxOrd)
                              throws java.io.IOException
        Description copied from interface: HnswBuilder
        Adds all nodes to the graph up to the provided maxOrd.
        Specified by:
        build in interface HnswBuilder
        Parameters:
        maxOrd - The maximum ordinal (excluded) of the nodes to be added.
        Throws:
        java.io.IOException
      • addVectors

        protected void addVectors​(int minOrd,
                                  int maxOrd)
                           throws java.io.IOException
        add vectors in range [minOrd, maxOrd)
        Throws:
        java.io.IOException
      • addVectors

        private void addVectors​(int maxOrd)
                         throws java.io.IOException
        Throws:
        java.io.IOException
      • addGraphNode

        public void addGraphNode​(int node)
                          throws java.io.IOException
        Description copied from interface: HnswBuilder
        Inserts a doc with vector value to the graph
        Specified by:
        addGraphNode in interface HnswBuilder
        Throws:
        java.io.IOException
      • printGraphBuildStatus

        private long printGraphBuildStatus​(int node,
                                           long start,
                                           long t)
      • addDiverseNeighbors

        private void addDiverseNeighbors​(int level,
                                         int node,
                                         NeighborArray candidates)
                                  throws java.io.IOException
        Throws:
        java.io.IOException
      • selectAndLinkDiverse

        private boolean[] selectAndLinkDiverse​(NeighborArray neighbors,
                                               NeighborArray candidates,
                                               int maxConnOnLevel)
                                        throws java.io.IOException
        This method will select neighbors to add and return a mask telling the caller which candidates are selected
        Throws:
        java.io.IOException
      • diversityCheck

        private boolean diversityCheck​(int candidate,
                                       float score,
                                       NeighborArray neighbors)
                                throws java.io.IOException
        Parameters:
        candidate - the vector of a new candidate neighbor of a node n
        score - the score of the new candidate and node n, to be compared with scores of the candidate and n's neighbors
        neighbors - the neighbors selected so far
        Returns:
        whether the candidate is diverse given the existing neighbors
        Throws:
        java.io.IOException
      • findWorstNonDiverse

        private int findWorstNonDiverse​(NeighborArray neighbors,
                                        int nodeOrd)
                                 throws java.io.IOException
        Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours
        Throws:
        java.io.IOException
      • isWorstNonDiverse

        private boolean isWorstNonDiverse​(int candidateIndex,
                                          NeighborArray neighbors,
                                          int[] uncheckedIndexes,
                                          int uncheckedCursor)
                                   throws java.io.IOException
        Throws:
        java.io.IOException
      • getRandomGraphLevel

        private static int getRandomGraphLevel​(double ml,
                                               java.util.SplittableRandom random)