Module org.apache.lucene.backward_codecs

Package org.apache.lucene.backward_codecs.lucene90

Class Lucene90OnHeapHnswGraph

java.lang.Object

org.apache.lucene.util.hnsw.HnswGraph

org.apache.lucene.backward_codecs.lucene90.Lucene90OnHeapHnswGraph

public final class Lucene90OnHeapHnswGraph
extends HnswGraph

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

Fields

Modifier and Type	Field	Description
private Lucene90NeighborArray	cur
private final List<Lucene90NeighborArray>	graph
private final int	maxConn
private int	upto

Fields inherited from class org.apache.lucene.util.hnsw.HnswGraph

EMPTY

Constructor Summary

Constructors

Constructor	Description
Lucene90OnHeapHnswGraph(int maxConn)

Method Summary

Modifier and Type	Method	Description
(package private) int	addNode()
int	entryNode()	Returns graph's entry point on the top level *
Lucene90NeighborArray	getNeighbors(int node)	Returns the NeighborQueue connected to the given node.
HnswGraph.NodesIterator	getNodesOnLevel(int level)	Get all nodes on a given level as node 0th ordinals
int	nextNeighbor()	Iterates over the neighbor list.
int	numLevels()	Returns the number of levels of the graph
static 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 given level's target.
int	size()	Returns the number of nodes in the graph

Methods inherited from class org.apache.lucene.util.hnsw.HnswGraph

maxNodeId

Methods inherited from class java.lang.Object

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

Field Details

maxConn

private final int maxConn

graph

private final List<Lucene90NeighborArray> graph

upto

private int upto

cur

private Lucene90NeighborArray 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 vector

topK - the number of nodes to be returned

numSeed - the size of the queue maintained while searching, and controls the number of random entry points to sample

vectors - vector values

graphValues - 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, or null 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

public Lucene90NeighborArray getNeighbors(int node)

Returns the NeighborQueue 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

Specified by:

size in class HnswGraph

addNode

int addNode()

seek

public void seek(int level,
 int targetNode)

Description copied from class: HnswGraph

Move the pointer to exactly the given level's target. After this method returns, call HnswGraph.nextNeighbor() to return successive (ordered) connected node ordinals.

Specified by:

seek in class HnswGraph

Parameters:

level - level of the graph

targetNode - 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 calling HnswGraph.seek(int, int), which resets the iterator.

Specified by:

nextNeighbor in class HnswGraph

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

Specified by:

numLevels in class HnswGraph

entryNode

public int entryNode()

Description copied from class: HnswGraph

Returns graph's entry point on the top level *

Specified by:

entryNode in class HnswGraph

getNodesOnLevel

public HnswGraph.NodesIterator getNodesOnLevel(int level)

Description copied from class: HnswGraph

Get all nodes on a given level as node 0th ordinals

Specified by:

getNodesOnLevel in class HnswGraph

Parameters:

level - level for which to get all nodes

Returns:

an iterator over nodes where nextInt returns a next node on the level