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 class	HnswGraph.ArrayNodesIterator	NodesIterator that accepts nodes as an integer array.
static class	HnswGraph.CollectionNodesIterator	Nodes iterator based on set representation of nodes.
static 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
int	maxNodeId()	Returns max node id, inclusive, normally this value will be size - 1
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 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 < FloatVectorValues.size().

Throws:

IOException

size

public abstract int size()

Returns the number of nodes in the graph

maxNodeId

public int maxNodeId()

Returns max node id, inclusive, normally this value will be size - 1

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