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

    • Field Detail

      • EMPTY

        public static HnswGraph EMPTY
        Empty graph value
    • Constructor Detail

      • HnswGraph

        protected HnswGraph()
        Sole constructor
    • Method Detail

      • 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