Class NeighborArray


  • public class NeighborArray
    extends java.lang.Object
    NeighborArray encodes the neighbors of a node and their mutual scores in the HNSW graph as a pair of growable arrays. Nodes are arranged in the sorted order of their scores in descending order (if scoresDescOrder is true), or in the ascending order of their scores (if scoresDescOrder is false)
    • Field Detail

      • scoresDescOrder

        private final boolean scoresDescOrder
      • size

        private int size
      • scores

        private final float[] scores
      • nodes

        private final int[] nodes
      • sortedNodeSize

        private int sortedNodeSize
      • rwlock

        public final java.util.concurrent.locks.ReadWriteLock rwlock
    • Constructor Detail

      • NeighborArray

        public NeighborArray​(int maxSize,
                             boolean descOrder)
    • Method Detail

      • addInOrder

        public void addInOrder​(int newNode,
                               float newScore)
        Add a new node to the NeighborArray. The new node must be worse than all previously stored nodes. This cannot be called after addOutOfOrder(int, float)
      • addOutOfOrder

        public void addOutOfOrder​(int newNode,
                                  float newScore)
        Add node and newScore but do not insert as sorted
      • addAndEnsureDiversity

        public void addAndEnsureDiversity​(int newNode,
                                          float newScore,
                                          int nodeId,
                                          RandomVectorScorerSupplier scorerSupplier)
                                   throws java.io.IOException
        In addition to addOutOfOrder(int, float), this function will also remove the least-diverse node if the node array is full after insertion

        In multi-threading environment, this method need to be locked as it will be called by multiple threads while other add method is only supposed to be called by one thread.

        Parameters:
        nodeId - node Id of the owner of this NeighbourArray
        Throws:
        java.io.IOException
      • sort

        int[] sort​(RandomVectorScorer scorer)
            throws java.io.IOException
        Sort the array according to scores, and return the sorted indexes of previous unsorted nodes (unchecked nodes)
        Returns:
        indexes of newly sorted (unchecked) nodes, in ascending order, or null if the array is already fully sorted
        Throws:
        java.io.IOException
      • insertSortedInternal

        private int insertSortedInternal​(RandomVectorScorer scorer)
                                  throws java.io.IOException
        insert the first unsorted node into its sorted position
        Throws:
        java.io.IOException
      • insertSorted

        void insertSorted​(int newNode,
                          float newScore)
                   throws java.io.IOException
        This method is for test only.
        Throws:
        java.io.IOException
      • size

        public int size()
      • nodes

        public int[] nodes()
        Direct access to the internal list of node ids; provided for efficient writing of the graph
      • scores

        public float[] scores()
      • clear

        public void clear()
      • removeLast

        void removeLast()
      • removeIndex

        void removeIndex​(int idx)
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • ascSortFindRightMostInsertionPoint

        private int ascSortFindRightMostInsertionPoint​(float newScore,
                                                       int bound)
      • descSortFindRightMostInsertionPoint

        private int descSortFindRightMostInsertionPoint​(float newScore,
                                                        int bound)
      • findWorstNonDiverse

        private int findWorstNonDiverse​(int nodeOrd,
                                        RandomVectorScorerSupplier scorerSupplier)
                                 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,
                                          int[] uncheckedIndexes,
                                          int uncheckedCursor,
                                          RandomVectorScorerSupplier scorerSupplier)
                                   throws java.io.IOException
        Throws:
        java.io.IOException