Class Lucene90OnHeapHnswGraph
java.lang.Object
org.apache.lucene.util.hnsw.HnswGraph
org.apache.lucene.backward_codecs.lucene90.Lucene90OnHeapHnswGraph
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.-
Nested Class Summary
Nested classes/interfaces inherited from class org.apache.lucene.util.hnsw.HnswGraph
HnswGraph.ArrayNodesIterator, HnswGraph.CollectionNodesIterator, HnswGraph.NodesIterator
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Lucene90NeighborArray
private final List
<Lucene90NeighborArray> private final int
private int
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) int
addNode()
int
Returns graph's entry point on the top level *getNeighbors
(int node) Returns theNeighborQueue
connected to the given node.getNodesOnLevel
(int level) Get all nodes on a given level as node 0th ordinalsint
Iterates over the neighbor list.int
Returns the number of levels of the graphstatic NeighborQueue
search
(float[] query, int topK, int numSeed, RandomAccessVectorValues.Floats vectors, VectorSimilarityFunction similarityFunction, HnswGraph graphValues, Bits acceptOrds, long visitedLimit, SplittableRandom random) Searches for the nearest neighbors of a query vector.void
seek
(int level, int targetNode) Move the pointer to exactly the givenlevel
'starget
.int
size()
Returns the number of nodes in the graph
-
Field Details
-
maxConn
private final int maxConn -
graph
-
upto
private int upto -
cur
-
-
Constructor Details
-
Lucene90OnHeapHnswGraph
Lucene90OnHeapHnswGraph(int maxConn)
-
-
Method Details
-
search
public static NeighborQueue search(float[] query, int topK, int numSeed, RandomAccessVectorValues.Floats vectors, VectorSimilarityFunction similarityFunction, HnswGraph graphValues, Bits acceptOrds, long visitedLimit, SplittableRandom random) throws IOException Searches for the nearest neighbors of a query vector.- Parameters:
query
- search query vectortopK
- the number of nodes to be returnednumSeed
- the size of the queue maintained while searching, and controls the number of random entry points to samplevectors
- vector valuesgraphValues
- the graph values. May represent the entire graph, or a level in a hierarchical graph.acceptOrds
-Bits
that represents the allowed document ordinals to match, ornull
if they are all allowed to match.random
- a source of randomness, used for generating entry points to the graph- Returns:
- a priority queue holding the closest neighbors found
- Throws:
IOException
-
getNeighbors
Returns theNeighborQueue
connected to the given node.- Parameters:
node
- the node whose neighbors are returned
-
size
public int size()Description copied from class:HnswGraph
Returns the number of nodes in the graph -
addNode
int addNode() -
seek
public void seek(int level, int targetNode) Description copied from class:HnswGraph
Move the pointer to exactly the givenlevel
'starget
. After this method returns, callHnswGraph.nextNeighbor()
to return successive (ordered) connected node ordinals.- Specified by:
seek
in classHnswGraph
- Parameters:
level
- level of the graphtargetNode
- 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 callingHnswGraph.seek(int, int)
, which resets the iterator.- Specified by:
nextNeighbor
in classHnswGraph
- Returns:
- a node ordinal in the graph, or NO_MORE_DOCS if the iteration is complete.
-
numLevels
public int numLevels()Description copied from class:HnswGraph
Returns the number of levels of the graph -
entryNode
public int entryNode()Description copied from class:HnswGraph
Returns graph's entry point on the top level * -
getNodesOnLevel
Description copied from class:HnswGraph
Get all nodes on a given level as node 0th ordinals- Specified by:
getNodesOnLevel
in classHnswGraph
- Parameters:
level
- level for which to get all nodes- Returns:
- an iterator over nodes where
nextInt
returns a next node on the level
-