Module org.apache.lucene.core
Package org.apache.lucene.util.hnsw

Class OnHeapHnswGraph

java.lang.Object
org.apache.lucene.util.hnsw.HnswGraph
org.apache.lucene.util.hnsw.OnHeapHnswGraph
All Implemented Interfaces:
Accountable
public final class OnHeapHnswGraph extends HnswGraph implements Accountable
An HnswGraph where all nodes and connections are held in memory. This class is used to construct the HNSW graph before it's written to the index.

  • Field Details

    • numLevels

      private int numLevels

    • entryNode

      private int entryNode

    • nodesByLevel

      private final List<int[]> nodesByLevel

    • graph

      private final List<List<NeighborArray>> graph

    • nsize

      private final int nsize

    • nsize0

      private final int nsize0

    • upto

      private int upto

    • cur

      private NeighborArray cur

  • Constructor Details

    • OnHeapHnswGraph

      OnHeapHnswGraph(int M, int levelOfFirstNode)

  • Method Details

    • getNeighbors

      public NeighborArray getNeighbors(int level, int node)
      Returns the NeighborQueue connected to the given node.
      Parameters:
      level - level of the graph
      node - the node whose neighbors are returned, represented as an ordinal on the level 0.

    • size

      public int size()
      Description copied from class: HnswGraph
      Returns the number of nodes in the graph
      Specified by:
      size in class HnswGraph

    • addNode

      public void addNode(int level, int node)
      Add node on the given level
      Parameters:
      level - level to add a node on
      node - the node to add, represented as an ordinal on the level 0.

    • seek

      public void seek(int level, int targetNode)
      Description copied from class: HnswGraph
      Move the pointer to exactly the given level's target. After this method returns, call HnswGraph.nextNeighbor() to return successive (ordered) connected node ordinals.
      Specified by:
      seek in class HnswGraph
      Parameters:
      level - level of the graph
      targetNode - ordinal of a node in the graph, must be ≥ 0 and < FloatVectorValues.size().

    • nextNeighbor

      public int nextNeighbor()
      Description copied from class: HnswGraph
      Iterates over the neighbor list. It is illegal to call this method after it returns NO_MORE_DOCS without calling HnswGraph.seek(int, int), which resets the iterator.
      Specified by:
      nextNeighbor in class HnswGraph
      Returns:
      a node ordinal in the graph, or NO_MORE_DOCS if the iteration is complete.

    • numLevels

      public int numLevels()
      Returns the current number of levels in the graph
      Specified by:
      numLevels in class HnswGraph
      Returns:
      the current number of levels in the graph

    • entryNode

      public int entryNode()
      Returns the graph's current entry node on the top level shown as ordinals of the nodes on 0th level
      Specified by:
      entryNode in class HnswGraph
      Returns:
      the graph's current entry node on the top level

    • getNodesOnLevel

      public HnswGraph.NodesIterator getNodesOnLevel(int level)
      Description copied from class: HnswGraph
      Get all nodes on a given level as node 0th ordinals
      Specified by:
      getNodesOnLevel in class HnswGraph
      Parameters:
      level - level for which to get all nodes
      Returns:
      an iterator over nodes where nextInt returns a next node on the level

    • ramBytesUsed

      public long ramBytesUsed()
      Description copied from interface: Accountable
      Return the memory usage of this object in bytes. Negative values are illegal.
      Specified by:
      ramBytesUsed in interface Accountable