Package org.apache.lucene.util.hnsw

Class HnswGraphBuilder<T>

java.lang.Object

org.apache.lucene.util.hnsw.HnswGraphBuilder<T>

Type Parameters:

T - the type of vector

public final class HnswGraphBuilder<T>
extends Object

Builder for HNSW graph. See HnswGraph for a gloss on the algorithm and the meaning of the hyperparameters.

Field Summary

Fields

Modifier and Type	Field	Description
private final int	beamWidth
private static final long	DEFAULT_RAND_SEED	Default random seed for level generation *
private final HnswGraphSearcher<T>	graphSearcher
(package private) final OnHeapHnswGraph	hnsw
static final String	HNSW_COMPONENT	A name for the HNSW component for the info-stream *
private InfoStream	infoStream
private final int	M
private final double	ml
private final SplittableRandom	random
static long	randSeed	Random seed for level generation; public to expose for testing *
private final NeighborArray	scratch
private final VectorSimilarityFunction	similarityFunction
private final VectorEncoding	vectorEncoding
private final RandomAccessVectorValues	vectors
private final RandomAccessVectorValues	vectorsCopy

Constructor Summary

Constructors

Modifier	Constructor	Description
private	HnswGraphBuilder(RandomAccessVectorValues vectors, VectorEncoding vectorEncoding, VectorSimilarityFunction similarityFunction, int M, int beamWidth, long seed)	Reads all the vectors from a VectorValues, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.

Method Summary

Modifier and Type	Method	Description
private void	addDiverseNeighbors(int level, int node, NeighborQueue candidates)
void	addGraphNode(int node, RandomAccessVectorValues values)
void	addGraphNode(int node, T value)	Inserts a doc with vector value to the graph
private void	addVectors(RandomAccessVectorValues vectorsToAdd)
OnHeapHnswGraph	build(RandomAccessVectorValues vectorsToAdd)	Reads all the vectors from two copies of a random access VectorValues.
static HnswGraphBuilder<?>	create(RandomAccessVectorValues vectors, VectorEncoding vectorEncoding, VectorSimilarityFunction similarityFunction, int M, int beamWidth, long seed)
private boolean	diversityCheck(int candidate, float score, NeighborArray neighbors)
private int	findWorstNonDiverse(NeighborArray neighbors)	Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours
OnHeapHnswGraph	getGraph()
private static int	getRandomGraphLevel(double ml, SplittableRandom random)
private T	getValue(int node, RandomAccessVectorValues values)
private boolean	isDiverse(float[] candidate, NeighborArray neighbors, float score)
private boolean	isDiverse(int candidate, NeighborArray neighbors, float score)
private boolean	isDiverse(BytesRef candidate, NeighborArray neighbors, float score)
private boolean	isWorstNonDiverse(int candidateIndex, float[] candidateVector, NeighborArray neighbors)
private boolean	isWorstNonDiverse(int candidateIndex, BytesRef candidateVector, NeighborArray neighbors)
private boolean	isWorstNonDiverse(int candidateIndex, NeighborArray neighbors)
private void	popToScratch(NeighborQueue candidates)
private long	printGraphBuildStatus(int node, long start, long t)
private void	selectAndLinkDiverse(NeighborArray neighbors, NeighborArray candidates, int maxConnOnLevel)
void	setInfoStream(InfoStream infoStream)	Set info-stream to output debugging information *

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_RAND_SEED

private static final long DEFAULT_RAND_SEED

Default random seed for level generation *

See Also:

• Constant Field Values

HNSW_COMPONENT

public static final String HNSW_COMPONENT

A name for the HNSW component for the info-stream *

See Also:

• Constant Field Values

randSeed

public static long randSeed

Random seed for level generation; public to expose for testing *

M

private final int M

beamWidth

private final int beamWidth

ml

private final double ml

scratch

private final NeighborArray scratch

similarityFunction

private final VectorSimilarityFunction similarityFunction

vectorEncoding

private final VectorEncoding vectorEncoding

vectors

private final RandomAccessVectorValues vectors

random

private final SplittableRandom random

graphSearcher

private final HnswGraphSearcher<T> graphSearcher

hnsw

final OnHeapHnswGraph hnsw

infoStream

private InfoStream infoStream

vectorsCopy

private final RandomAccessVectorValues vectorsCopy

Constructor Details

HnswGraphBuilder

private HnswGraphBuilder(RandomAccessVectorValues vectors,
 VectorEncoding vectorEncoding,
 VectorSimilarityFunction similarityFunction,
 int M,
 int beamWidth,
 long seed)
                  throws IOException

Reads all the vectors from a VectorValues, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.

Parameters:

vectors - the vectors whose relations are represented by the graph - must provide a different view over those vectors than the one used to add via addGraphNode.

M - – graph fanout parameter used to calculate the maximum number of connections a node can have – M on upper layers, and M * 2 on the lowest level.

beamWidth - the size of the beam search to use when finding nearest neighbors.

seed - the seed for a random number generator used during graph construction. Provide this to ensure repeatable construction.

Throws:

IOException

Method Details

create

public static HnswGraphBuilder<?> create(RandomAccessVectorValues vectors,
 VectorEncoding vectorEncoding,
 VectorSimilarityFunction similarityFunction,
 int M,
 int beamWidth,
 long seed)
                                  throws IOException

Throws:

IOException

build

public OnHeapHnswGraph build(RandomAccessVectorValues vectorsToAdd)
                      throws IOException

Reads all the vectors from two copies of a random access VectorValues. Providing two copies enables efficient retrieval without extra data copying, while avoiding collision of the returned values.

Parameters:

vectorsToAdd - the vectors for which to build a nearest neighbors graph. Must be an independent accessor for the vectors

Throws:

IOException

addVectors

private void addVectors(RandomAccessVectorValues vectorsToAdd)
                 throws IOException

Throws:

IOException

setInfoStream

public void setInfoStream(InfoStream infoStream)

Set info-stream to output debugging information *

getGraph

public OnHeapHnswGraph getGraph()

addGraphNode

public void addGraphNode(int node,
 T value)
                  throws IOException

Inserts a doc with vector value to the graph

Throws:

IOException

addGraphNode

public void addGraphNode(int node,
 RandomAccessVectorValues values)
                  throws IOException

Throws:

IOException

getValue

private T getValue(int node,
 RandomAccessVectorValues values)
            throws IOException

Throws:

IOException

printGraphBuildStatus

private long printGraphBuildStatus(int node,
 long start,
 long t)

addDiverseNeighbors

private void addDiverseNeighbors(int level,
 int node,
 NeighborQueue candidates)
                          throws IOException

Throws:

IOException

selectAndLinkDiverse

private void selectAndLinkDiverse(NeighborArray neighbors,
 NeighborArray candidates,
 int maxConnOnLevel)
                           throws IOException

Throws:

IOException

popToScratch

private void popToScratch(NeighborQueue candidates)

diversityCheck

private boolean diversityCheck(int candidate,
 float score,
 NeighborArray neighbors)
                        throws IOException

Parameters:

candidate - the vector of a new candidate neighbor of a node n

score - the score of the new candidate and node n, to be compared with scores of the candidate and n's neighbors

neighbors - the neighbors selected so far

Returns:

whether the candidate is diverse given the existing neighbors

Throws:

IOException

isDiverse

private boolean isDiverse(int candidate,
 NeighborArray neighbors,
 float score)
                   throws IOException

Throws:

IOException

isDiverse

private boolean isDiverse(float[] candidate,
 NeighborArray neighbors,
 float score)
                   throws IOException

Throws:

IOException

isDiverse

private boolean isDiverse(BytesRef candidate,
 NeighborArray neighbors,
 float score)
                   throws IOException

Throws:

IOException

findWorstNonDiverse

private int findWorstNonDiverse(NeighborArray neighbors)
                         throws IOException

Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours

Throws:

IOException

isWorstNonDiverse

private boolean isWorstNonDiverse(int candidateIndex,
 NeighborArray neighbors)
                           throws IOException

Throws:

IOException

isWorstNonDiverse

private boolean isWorstNonDiverse(int candidateIndex,
 float[] candidateVector,
 NeighborArray neighbors)
                           throws IOException

Throws:

IOException

isWorstNonDiverse

private boolean isWorstNonDiverse(int candidateIndex,
 BytesRef candidateVector,
 NeighborArray neighbors)
                           throws IOException

Throws:

IOException

getRandomGraphLevel

private static int getRandomGraphLevel(double ml,
 SplittableRandom random)