java.lang.Object
org.apache.lucene.util.hnsw.NeighborQueue
NeighborQueue uses a
LongHeap
to store lists of arcs in an HNSW graph, represented as a
neighbor node id with an associated score packed together as a sortable long, which is sorted
primarily by score. The queue provides both fixed-size and unbounded operations via insertWithOverflow(int, float)
and add(int, float)
, and provides MIN and MAX heap
subclasses.-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final LongHeap
private boolean
private final NeighborQueue.Order
private int
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
add
(int newNode, float newScore) Adds a new graph arc, extending the storage as needed.void
clear()
private int
decodeNodeId
(long heapValue) private float
decodeScore
(long heapValue) private long
encode
(int node, float score) Encodes the node ID and its similarity score as long, preserving the Lucene tie-breaking rule that when two scores are equals, the smaller node ID must win.boolean
boolean
insertWithOverflow
(int newNode, float newScore) If the heap is not full (size is less than the initialSize provided to the constructor), adds a new node-and-score element.void
int[]
nodes()
int
pop()
Removes the top element and returns its node id.void
setVisitedCount
(int visitedCount) int
size()
int
topNode()
Returns the top element's node id.float
topScore()
Returns the top element's node score.toString()
int
-
Field Details
-
heap
-
order
-
visitedCount
private int visitedCount -
incomplete
private boolean incomplete
-
-
Constructor Details
-
NeighborQueue
public NeighborQueue(int initialSize, boolean maxHeap)
-
-
Method Details
-
size
public int size()- Returns:
- the number of elements in the heap
-
add
public void add(int newNode, float newScore) Adds a new graph arc, extending the storage as needed.- Parameters:
newNode
- the neighbor node idnewScore
- the score of the neighbor, relative to some other node
-
insertWithOverflow
public boolean insertWithOverflow(int newNode, float newScore) If the heap is not full (size is less than the initialSize provided to the constructor), adds a new node-and-score element. If the heap is full, compares the score against the current top score, and replaces the top element if newScore is better than (greater than unless the heap is reversed), the current top score.- Parameters:
newNode
- the neighbor node idnewScore
- the score of the neighbor, relative to some other node
-
encode
private long encode(int node, float score) Encodes the node ID and its similarity score as long, preserving the Lucene tie-breaking rule that when two scores are equals, the smaller node ID must win.The most significant 32 bits represent the float score, encoded as a sortable int.
The less significant 32 bits represent the node ID.
The bits representing the node ID are complemented to guarantee the win for the smaller node Id.
The AND with 0xFFFFFFFFL (a long with first 32 bit as 1) is necessary to obtain a long that has
The most significant 32 bits to 0
The less significant 32 bits represent the node ID.
- Parameters:
node
- the node IDscore
- the node score- Returns:
- the encoded score, node ID
-
decodeScore
private float decodeScore(long heapValue) -
decodeNodeId
private int decodeNodeId(long heapValue) -
pop
public int pop()Removes the top element and returns its node id. -
nodes
public int[] nodes() -
topNode
public int topNode()Returns the top element's node id. -
topScore
public float topScore()Returns the top element's node score. For the min heap this is the minimum score. For the max heap this is the maximum score. -
clear
public void clear() -
visitedCount
public int visitedCount() -
setVisitedCount
public void setVisitedCount(int visitedCount) -
incomplete
public boolean incomplete() -
markIncomplete
public void markIncomplete() -
toString
-