Package org.apache.lucene.util.hnsw
Class HnswGraphBuilder
java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphBuilder
Builder for HNSW graph. See
HnswGraph
for a gloss on the algorithm and the meaning of the
hyperparameters.-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final int
private final BoundsChecker
private RandomAccessVectorValues
private static final long
Default random seed for level generation *private final HnswGraphSearcher
(package private) final OnHeapHnswGraph
static final String
A name for the HNSW component for the info-stream *private InfoStream
private final int
private final double
private final SplittableRandom
static long
Random seed for level generation; public to expose for testing *private final NeighborArray
private final VectorSimilarityFunction
private final RandomAccessVectorValues
-
Constructor Summary
ConstructorsConstructorDescriptionHnswGraphBuilder
(RandomAccessVectorValuesProducer vectors, 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 TypeMethodDescriptionprivate void
addDiverseNeighbors
(int level, int node, NeighborQueue candidates) (package private) void
addGraphNode
(int node, float[] value) Inserts a doc with vector value to the graphbuild
(RandomAccessVectorValues vectors) Reads all the vectors from two copies of a random access VectorValues.private boolean
diversityCheck
(float[] candidate, float score, NeighborArray neighbors, RandomAccessVectorValues vectorValues) private int
findWorstNonDiverse
(NeighborArray neighbors) Find first non-diverse neighbour among the list of neighbors starting from the most distant neighboursprivate static int
getRandomGraphLevel
(double ml, SplittableRandom random) 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 *
-
Field Details
-
DEFAULT_RAND_SEED
private static final long DEFAULT_RAND_SEEDDefault random seed for level generation *- See Also:
-
HNSW_COMPONENT
A name for the HNSW component for the info-stream *- See Also:
-
randSeed
public static long randSeedRandom 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
-
similarityFunction
-
vectorValues
-
random
-
bound
-
graphSearcher
-
hnsw
-
infoStream
-
buildVectors
-
-
Constructor Details
-
HnswGraphBuilder
public HnswGraphBuilder(RandomAccessVectorValuesProducer vectors, 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
-
build
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:
vectors
- the vectors for which to build a nearest neighbors graph. Must be an independet accessor for the vectors- Throws:
IOException
-
setInfoStream
Set info-stream to output debugging information * -
addGraphNode
Inserts a doc with vector value to the graph- Throws:
IOException
-
printGraphBuildStatus
private long printGraphBuildStatus(int node, long start, long t) -
addDiverseNeighbors
- Throws:
IOException
-
selectAndLinkDiverse
private void selectAndLinkDiverse(NeighborArray neighbors, NeighborArray candidates, int maxConnOnLevel) throws IOException - Throws:
IOException
-
popToScratch
-
diversityCheck
private boolean diversityCheck(float[] candidate, float score, NeighborArray neighbors, RandomAccessVectorValues vectorValues) throws IOException - Parameters:
candidate
- the vector of a new candidate neighbor of a node nscore
- the score of the new candidate and node n, to be compared with scores of the candidate and n's neighborsneighbors
- the neighbors selected so farvectorValues
- source of values used for making comparisons between candidate and existing neighbors- Returns:
- whether the candidate is diverse given the existing neighbors
- Throws:
IOException
-
findWorstNonDiverse
Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours- Throws:
IOException
-
getRandomGraphLevel
-