Class Lucene90HnswGraphBuilder


  • public final class Lucene90HnswGraphBuilder
    extends java.lang.Object
    Builder for HNSW graph. See Lucene90OnHeapHnswGraph for a gloss on the algorithm and the meaning of the hyperparameters.

    This class is preserved here only for tests.

    • Constructor Detail

      • Lucene90HnswGraphBuilder

        public Lucene90HnswGraphBuilder​(RandomAccessVectorValues.Floats vectors,
                                        VectorSimilarityFunction similarityFunction,
                                        int maxConn,
                                        int beamWidth,
                                        long seed)
                                 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:
        vectors - the vectors whose relations are represented by the graph - must provide a different view over those vectors than the one used to add via addGraphNode.
        maxConn - the number of connections to make when adding a new graph node; roughly speaking the graph fanout.
        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.
        Throws:
        java.io.IOException
    • Method Detail

      • build

        public Lucene90OnHeapHnswGraph build​(RandomAccessVectorValues.Floats vectors)
                                      throws java.io.IOException
        Reads all the vectors from two copies of a RandomAccessVectorValues. Providing two copies enables efficient retrieval without extra data copying, while avoiding collision of the returned values.
        Parameters:
        vectors - the vectors for which to build a nearest neighbors graph. Must be an independet accessor for the vectors
        Throws:
        java.io.IOException
      • setInfoStream

        public void setInfoStream​(InfoStream infoStream)
        Set info-stream to output debugging information *
      • addGraphNode

        void addGraphNode​(float[] value)
                   throws java.io.IOException
        Inserts a doc with vector value to the graph
        Throws:
        java.io.IOException
      • addDiverseNeighbors

        private void addDiverseNeighbors​(int node,
                                         NeighborQueue candidates)
                                  throws java.io.IOException
        Throws:
        java.io.IOException
      • popToScratch

        private void popToScratch​(NeighborQueue candidates)
      • diversityCheck

        private boolean diversityCheck​(float[] candidate,
                                       float score,
                                       Lucene90NeighborArray neighbors,
                                       RandomAccessVectorValues.Floats vectorValues)
                                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
        vectorValues - source of values used for making comparisons between candidate and existing neighbors
        Returns:
        whether the candidate is diverse given the existing neighbors
        Throws:
        java.io.IOException
      • diversityUpdate

        private void diversityUpdate​(Lucene90NeighborArray neighbors)
                              throws java.io.IOException
        Throws:
        java.io.IOException
      • findNonDiverse

        private int findNonDiverse​(Lucene90NeighborArray neighbors)
                            throws java.io.IOException
        Throws:
        java.io.IOException