Package org.apache.lucene.util.hnsw

Class HnswGraph

java.lang.Object
org.apache.lucene.util.hnsw.HnswGraph
Direct Known Subclasses:
OnHeapHnswGraph
public abstract class HnswGraph extends Object
Hierarchical Navigable Small World graph. Provides efficient approximate nearest neighbor search for high dimensional vectors. See Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs [2018] paper for details.

The nomenclature is a bit different here from what's used in the paper:

Hyperparameters

  • beamWidth in HnswGraphBuilder has the same meaning as efConst in the paper. It is the number of nearest neighbor candidates to track while searching the graph for each newly inserted node.
  • maxConn has the same meaning as M in the paper; it controls how many of the efConst neighbors are connected to the new node

Note: The graph may be searched by multiple threads concurrently, but updates are not thread-safe. The search method optionally takes a set of "accepted nodes", which can be used to exclude deleted documents.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    HnswGraph.NodesIterator
    Iterator over the graph nodes on a certain level, Iterator also provides the size – the total number of nodes to be iterated over.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static HnswGraph
    EMPTY
    Empty graph value

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    HnswGraph()
    Sole constructor

  • Method Summary

    Modifier and Type
    Method
    Description
    abstract int
    entryNode()
    Returns graph's entry point on the top level *
    abstract HnswGraph.NodesIterator
    getNodesOnLevel(int level)
    Get all nodes on a given level as node 0th ordinals
    abstract int
    nextNeighbor()
    Iterates over the neighbor list.
    abstract int
    numLevels()
    Returns the number of levels of the graph
    abstract void
    seek(int level, int target)
    Move the pointer to exactly the given level's target.
    abstract int
    size()
    Returns the number of nodes in the graph

    Methods inherited from class java.lang.Object

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

  • Field Details

    • EMPTY

      public static HnswGraph EMPTY
      Empty graph value

  • Constructor Details

    • HnswGraph

      protected HnswGraph()
      Sole constructor

  • Method Details

    • seek

      public abstract void seek(int level, int target) throws IOException
      Move the pointer to exactly the given level's target. After this method returns, call nextNeighbor() to return successive (ordered) connected node ordinals.
      Parameters:
      level - level of the graph
      target - ordinal of a node in the graph, must be ≥ 0 and < VectorValues.size().
      Throws:
      IOException

    • size

      public abstract int size()
      Returns the number of nodes in the graph

    • nextNeighbor

      public abstract int nextNeighbor() throws IOException
      Iterates over the neighbor list. It is illegal to call this method after it returns NO_MORE_DOCS without calling seek(int, int), which resets the iterator.
      Returns:
      a node ordinal in the graph, or NO_MORE_DOCS if the iteration is complete.
      Throws:
      IOException

    • numLevels

      public abstract int numLevels() throws IOException
      Returns the number of levels of the graph
      Throws:
      IOException

    • entryNode

      public abstract int entryNode() throws IOException
      Returns graph's entry point on the top level *
      Throws:
      IOException

    • getNodesOnLevel

      public abstract HnswGraph.NodesIterator getNodesOnLevel(int level) throws IOException
      Get all nodes on a given level as node 0th ordinals
      Parameters:
      level - level for which to get all nodes
      Returns:
      an iterator over nodes where nextInt returns a next node on the level
      Throws:
      IOException