Package org.apache.lucene.util.hnsw

Class NeighborQueue

  • public class NeighborQueue
extends java.lang.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 class  NeighborQueue.Order  

    • Constructor Summary

      Constructors 
      Constructor Description
      NeighborQueue​(int initialSize, boolean reversed)  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int newNode, float newScore)
      Adds a new graph arc, extending the storage as needed.
      void clear()  
      private long encode​(int node, float score)  
      boolean incomplete()  
      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 markIncomplete()  
      int[] nodes()  
      int pop()
      Removes the top element and returns its node id.
      void setVisitedCount​(int visitedCount)  
      int size()  
      int topNode()
      Returns the top element's node id.
      float topScore()
      Returns the top element's node score.
      java.lang.String toString()  
      int visitedCount()  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    • Field Detail

      • visitedCount

        private int visitedCount

      • incomplete

        private boolean incomplete

    • Constructor Detail

      • NeighborQueue

        public NeighborQueue​(int initialSize,
                     boolean reversed)

    • Method Detail

      • 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)

      • 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.

      • clear

        public void clear()

      • visitedCount

        public int visitedCount()

      • setVisitedCount

        public void setVisitedCount​(int visitedCount)

      • incomplete

        public boolean incomplete()

      • markIncomplete

        public void markIncomplete()

      • toString

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