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.
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private static enum 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final LongHeap
     
    private boolean
     
    private final NeighborQueue.Order
     
    private int
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    NeighborQueue(int initialSize, boolean maxHeap)
     
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(int newNode, float newScore)
    Adds a new graph arc, extending the storage as needed.
    void
     
    private int
    decodeNodeId(long heapValue)
     
    private float
    decodeScore(long heapValue)
     
    private long
    encode(int node, float score)
    Encodes the node ID and its similarity score as long, preserving the Lucene tie-breaking rule that when two scores are equals, the smaller node ID must win.
    boolean
     
    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.
    void
     
    int[]
     
    int
    pop()
    Removes the top element and returns its node id.
    void
    setVisitedCount(int visitedCount)
     
    int
     
    int
    Returns the top element's node id.
    float
    Returns the top element's node score.
     
    int
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Field Details

    • heap

      private final LongHeap heap
    • order

      private final NeighborQueue.Order order
    • visitedCount

      private int visitedCount
    • incomplete

      private boolean incomplete
  • Constructor Details

    • NeighborQueue

      public NeighborQueue(int initialSize, boolean maxHeap)
  • 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
    • encode

      private long encode(int node, float score)
      Encodes the node ID and its similarity score as long, preserving the Lucene tie-breaking rule that when two scores are equals, the smaller node ID must win.

      The most significant 32 bits represent the float score, encoded as a sortable int.

      The less significant 32 bits represent the node ID.

      The bits representing the node ID are complemented to guarantee the win for the smaller node Id.

      The AND with 0xFFFFFFFFL (a long with first 32 bit as 1) is necessary to obtain a long that has

      The most significant 32 bits to 0

      The less significant 32 bits represent the node ID.

      Parameters:
      node - the node ID
      score - the node score
      Returns:
      the encoded score, node ID
    • decodeScore

      private float decodeScore(long heapValue)
    • decodeNodeId

      private int decodeNodeId(long heapValue)
    • pop

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

      public int[] nodes()
    • topNode

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

      public float topScore()
      Returns the top element's node score. For the min heap this is the minimum score. For the max heap this is the maximum 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