- java.lang.Object
-
- org.apache.lucene.util.hnsw.NeighborArray
-
public class NeighborArray extends java.lang.Object
NeighborArray encodes the neighbors of a node and their mutual scores in the HNSW graph as a pair of growable arrays. Nodes are arranged in the sorted order of their scores in descending order (if scoresDescOrder is true), or in the ascending order of their scores (if scoresDescOrder is false)
-
-
Field Summary
Fields Modifier and Type Field Description private int[]
nodes
java.util.concurrent.locks.ReadWriteLock
rwlock
private float[]
scores
private boolean
scoresDescOrder
private int
size
private int
sortedNodeSize
-
Constructor Summary
Constructors Constructor Description NeighborArray(int maxSize, boolean descOrder)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addAndEnsureDiversity(int newNode, float newScore, int nodeId, RandomVectorScorerSupplier scorerSupplier)
In addition toaddOutOfOrder(int, float)
, this function will also remove the least-diverse node if the node array is full after insertionvoid
addInOrder(int newNode, float newScore)
Add a new node to the NeighborArray.void
addOutOfOrder(int newNode, float newScore)
Add node and newScore but do not insert as sortedprivate int
ascSortFindRightMostInsertionPoint(float newScore, int bound)
void
clear()
private int
descSortFindRightMostInsertionPoint(float newScore, int bound)
private int
findWorstNonDiverse(int nodeOrd, RandomVectorScorerSupplier scorerSupplier)
Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours(package private) void
insertSorted(int newNode, float newScore)
This method is for test only.private int
insertSortedInternal(RandomVectorScorer scorer)
insert the first unsorted node into its sorted positionprivate boolean
isWorstNonDiverse(int candidateIndex, int[] uncheckedIndexes, int uncheckedCursor, RandomVectorScorerSupplier scorerSupplier)
int[]
nodes()
Direct access to the internal list of node ids; provided for efficient writing of the graph(package private) void
removeIndex(int idx)
(package private) void
removeLast()
float[]
scores()
int
size()
(package private) int[]
sort(RandomVectorScorer scorer)
Sort the array according to scores, and return the sorted indexes of previous unsorted nodes (unchecked nodes)java.lang.String
toString()
-
-
-
Method Detail
-
addInOrder
public void addInOrder(int newNode, float newScore)
Add a new node to the NeighborArray. The new node must be worse than all previously stored nodes. This cannot be called afteraddOutOfOrder(int, float)
-
addOutOfOrder
public void addOutOfOrder(int newNode, float newScore)
Add node and newScore but do not insert as sorted
-
addAndEnsureDiversity
public void addAndEnsureDiversity(int newNode, float newScore, int nodeId, RandomVectorScorerSupplier scorerSupplier) throws java.io.IOException
In addition toaddOutOfOrder(int, float)
, this function will also remove the least-diverse node if the node array is full after insertionIn multi-threading environment, this method need to be locked as it will be called by multiple threads while other add method is only supposed to be called by one thread.
- Parameters:
nodeId
- node Id of the owner of this NeighbourArray- Throws:
java.io.IOException
-
sort
int[] sort(RandomVectorScorer scorer) throws java.io.IOException
Sort the array according to scores, and return the sorted indexes of previous unsorted nodes (unchecked nodes)- Returns:
- indexes of newly sorted (unchecked) nodes, in ascending order, or null if the array is already fully sorted
- Throws:
java.io.IOException
-
insertSortedInternal
private int insertSortedInternal(RandomVectorScorer scorer) throws java.io.IOException
insert the first unsorted node into its sorted position- Throws:
java.io.IOException
-
insertSorted
void insertSorted(int newNode, float newScore) throws java.io.IOException
This method is for test only.- Throws:
java.io.IOException
-
size
public int size()
-
nodes
public int[] nodes()
Direct access to the internal list of node ids; provided for efficient writing of the graph
-
scores
public float[] scores()
-
clear
public void clear()
-
removeLast
void removeLast()
-
removeIndex
void removeIndex(int idx)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
ascSortFindRightMostInsertionPoint
private int ascSortFindRightMostInsertionPoint(float newScore, int bound)
-
descSortFindRightMostInsertionPoint
private int descSortFindRightMostInsertionPoint(float newScore, int bound)
-
findWorstNonDiverse
private int findWorstNonDiverse(int nodeOrd, RandomVectorScorerSupplier scorerSupplier) throws java.io.IOException
Find first non-diverse neighbour among the list of neighbors starting from the most distant neighbours- Throws:
java.io.IOException
-
isWorstNonDiverse
private boolean isWorstNonDiverse(int candidateIndex, int[] uncheckedIndexes, int uncheckedCursor, RandomVectorScorerSupplier scorerSupplier) throws java.io.IOException
- Throws:
java.io.IOException
-
-