java.lang.Object
org.apache.lucene.util.hnsw.HnswGraphBuilder
- All Implemented Interfaces:
HnswBuilder
- Direct Known Subclasses:
HnswConcurrentMergeBuilder.ConcurrentMergeWorker
,InitializedHnswGraphBuilder
Builder for HNSW graph. See
HnswGraph
for a gloss on the algorithm and the meaning of the
hyper-parameters.-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic final class
A restricted, specialized knnCollector that can be used when building a graph. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final HnswGraphBuilder.GraphBuilderKnnCollector
static final int
Default number of the size of the queue maintained while searching during a graph construction.static final int
Default number of maximum connections per nodeprivate static final long
Default random seed for level generation *private final HnswGraphBuilder.GraphBuilderKnnCollector
private final HnswGraphSearcher
protected 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 RandomVectorScorerSupplier
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
HnswGraphBuilder
(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, int graphSize) Reads all the vectors from vector values, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.protected
HnswGraphBuilder
(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, OnHeapHnswGraph hnsw) protected
HnswGraphBuilder
(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, OnHeapHnswGraph hnsw, HnswGraphSearcher graphSearcher) Reads all the vectors from vector values, 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, NeighborArray candidates) void
addGraphNode
(int node) Inserts a doc with vector value to the graphprivate void
addVectors
(int maxOrd) protected void
addVectors
(int minOrd, int maxOrd) add vectors in range [minOrd, maxOrd)build
(int maxOrd) Adds all nodes to the graph up to the providedmaxOrd
.static HnswGraphBuilder
create
(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed) static HnswGraphBuilder
create
(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, int graphSize) private boolean
diversityCheck
(int candidate, float score, NeighborArray neighbors) getGraph()
private static int
getRandomGraphLevel
(double ml, SplittableRandom random) private static void
popToScratch
(HnswGraphBuilder.GraphBuilderKnnCollector candidates, NeighborArray scratch) private long
printGraphBuildStatus
(int node, long start, long t) private boolean[]
selectAndLinkDiverse
(NeighborArray neighbors, NeighborArray candidates, int maxConnOnLevel) This method will select neighbors to add and return a mask telling the caller which candidates are selectedvoid
setInfoStream
(InfoStream infoStream) Set info-stream to output debugging information
-
Field Details
-
DEFAULT_MAX_CONN
public static final int DEFAULT_MAX_CONNDefault number of maximum connections per node- See Also:
-
DEFAULT_BEAM_WIDTH
public static final int DEFAULT_BEAM_WIDTHDefault number of the size of the queue maintained while searching during a graph construction.- See Also:
-
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 -
ml
private final double ml -
random
-
scorerSupplier
-
graphSearcher
-
entryCandidates
-
beamCandidates
-
hnsw
-
infoStream
-
-
Constructor Details
-
HnswGraphBuilder
protected HnswGraphBuilder(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, int graphSize) throws IOException Reads all the vectors from vector values, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.- Parameters:
scorerSupplier
- a supplier to create vector scorer from ordinals.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.graphSize
- size of graph, if unknown, pass in -1- Throws:
IOException
-
HnswGraphBuilder
protected HnswGraphBuilder(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, OnHeapHnswGraph hnsw) throws IOException - Throws:
IOException
-
HnswGraphBuilder
protected HnswGraphBuilder(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, OnHeapHnswGraph hnsw, HnswGraphSearcher graphSearcher) throws IOException Reads all the vectors from vector values, builds a graph connecting them by their dense ordinals, using the given hyperparameter settings, and returns the resulting graph.- Parameters:
scorerSupplier
- a supplier to create vector scorer from ordinals.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.hnsw
- the graph to build, can be previously initialized- Throws:
IOException
-
-
Method Details
-
create
public static HnswGraphBuilder create(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed) throws IOException - Throws:
IOException
-
create
public static HnswGraphBuilder create(RandomVectorScorerSupplier scorerSupplier, int M, int beamWidth, long seed, int graphSize) throws IOException - Throws:
IOException
-
build
Description copied from interface:HnswBuilder
Adds all nodes to the graph up to the providedmaxOrd
.- Specified by:
build
in interfaceHnswBuilder
- Parameters:
maxOrd
- The maximum ordinal (excluded) of the nodes to be added.- Throws:
IOException
-
setInfoStream
Description copied from interface:HnswBuilder
Set info-stream to output debugging information- Specified by:
setInfoStream
in interfaceHnswBuilder
-
getGraph
- Specified by:
getGraph
in interfaceHnswBuilder
-
addVectors
add vectors in range [minOrd, maxOrd)- Throws:
IOException
-
addVectors
- Throws:
IOException
-
addGraphNode
Description copied from interface:HnswBuilder
Inserts a doc with vector value to the graph- Specified by:
addGraphNode
in interfaceHnswBuilder
- Throws:
IOException
-
printGraphBuildStatus
private long printGraphBuildStatus(int node, long start, long t) -
addDiverseNeighbors
- Throws:
IOException
-
selectAndLinkDiverse
private boolean[] selectAndLinkDiverse(NeighborArray neighbors, NeighborArray candidates, int maxConnOnLevel) throws IOException This method will select neighbors to add and return a mask telling the caller which candidates are selected- Throws:
IOException
-
popToScratch
private static void popToScratch(HnswGraphBuilder.GraphBuilderKnnCollector candidates, NeighborArray scratch) -
diversityCheck
private boolean diversityCheck(int candidate, float score, NeighborArray neighbors) 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 far- Returns:
- whether the candidate is diverse given the existing neighbors
- Throws:
IOException
-
getRandomGraphLevel
-