Package org.apache.lucene.util.hnsw

Class NeighborQueue

java.lang.Object
org.apache.lucene.util.hnsw.NeighborQueue
public class NeighborQueue extends Object
NeighborQueue uses a LongHeap to store lists of arcs in an HNSW graph, represented as a neighbor node id with an associated score packed together as a sortable long, which is sorted primarily by score. The queue provides both fixed-size and unbounded operations via insertWithOverflow(int, float) and add(int, float), and provides MIN and MAX heap subclasses.

  • Constructor Details

    • NeighborQueue

      public NeighborQueue(int initialSize, boolean reversed)

  • Method Details

    • size

      public int size()
      Returns:
      the number of elements in the heap

    • add

      public void add(int newNode, float newScore)
      Adds a new graph arc, extending the storage as needed.
      Parameters:
      newNode - the neighbor node id
      newScore - the score of the neighbor, relative to some other node

    • insertWithOverflow

      public boolean insertWithOverflow(int newNode, float newScore)
      If the heap is not full (size is less than the initialSize provided to the constructor), adds a new node-and-score element. If the heap is full, compares the score against the current top score, and replaces the top element if newScore is better than (greater than unless the heap is reversed), the current top score.
      Parameters:
      newNode - the neighbor node id
      newScore - the score of the neighbor, relative to some other node

    • pop

      public int pop()
      Removes the top element and returns its node id.

    • topNode

      public int topNode()
      Returns the top element's node id.

    • topScore

      public float topScore()
      Returns the top element's node score.

    • clear

      public void clear()

    • visitedCount

      public int visitedCount()

    • setVisitedCount

      public void setVisitedCount(int visitedCount)

    • incomplete

      public boolean incomplete()

    • markIncomplete

      public void markIncomplete()

    • toString

      public String toString()
      Overrides:
      toString in class Object