Class NeighborArray

java.lang.Object
org.apache.lucene.util.hnsw.NeighborArray

public class NeighborArray extends 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 Details

    • scoresDescOrder

      private final boolean scoresDescOrder
    • size

      private int size
    • scores

      private final float[] scores
    • nodes

      private final int[] nodes
    • sortedNodeSize

      private int sortedNodeSize
  • Constructor Details

    • NeighborArray

      public NeighborArray(int maxSize, boolean descOrder)
  • Method Details

    • 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 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:
      IOException
    • sort

      int[] sort(RandomVectorScorer scorer) throws 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:
      IOException
    • insertSortedInternal

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

      void insertSorted(int newNode, float newScore) throws IOException
      This method is for test only.
      Throws:
      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 String toString()
      Overrides:
      toString in class 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 IOException
      Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours
      Throws:
      IOException
    • isWorstNonDiverse

      private boolean isWorstNonDiverse(int candidateIndex, int[] uncheckedIndexes, int uncheckedCursor, RandomVectorScorerSupplier scorerSupplier) throws IOException
      Throws:
      IOException