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
inHnswGraphBuilder
has the same meaning asefConst
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 asM
in the paper; it controls how many of theefConst
neighbors are connected to the new node
Note: The graph may be searched by multiple threads concurrently, but updates are not threadsafe. 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.NodesIterator
Iterator over the graph nodes on a certain level, Iterator also provides the size – the total number of nodes to be iterated over.

Constructor Summary
Constructors Modifier Constructor Description protected
HnswGraph()
Sole constructor

Method Summary
All Methods Instance Methods Abstract Methods 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 ordinalsabstract int
nextNeighbor()
Iterates over the neighbor list.abstract int
numLevels()
Returns the number of levels of the graphabstract void
seek(int level, int target)
Move the pointer to exactly the givenlevel
'starget
.abstract int
size()
Returns the number of nodes in the graph



Field Detail

EMPTY
public static HnswGraph EMPTY
Empty graph value


Method Detail

seek
public abstract void seek(int level, int target) throws IOException
Move the pointer to exactly the givenlevel
'starget
. After this method returns, callnextNeighbor()
to return successive (ordered) connected node ordinals. Parameters:
level
 level of the graphtarget
 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 callingseek(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

