mayya-sharipova commented on a change in pull request #250:
URL: https://github.com/apache/lucene/pull/250#discussion_r693488482
##########
File path: lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java
##########
@@ -166,25 +173,35 @@ public static NeighborQueue search(
/**
* Returns the {@link NeighborQueue} connected to the given node.
*
+ * @param level level of the graph
* @param node the node whose neighbors are returned
*/
- public NeighborArray getNeighbors(int node) {
- return graph.get(node);
+ public NeighborArray getNeighbors(int level, int node) {
+ NeighborArray result = graph.get(level).get(node);
+ assert result != null;
+ return result;
}
@Override
public int size() {
- return graph.size();
+ return graph.get(0).size(); // all nodes are located on the 0th level
}
- int addNode() {
- graph.add(new NeighborArray(maxConn + 1));
- return graph.size() - 1;
+ public void addNode(int level, int node) {
+ if (level > 0) {
+ // Levels above 0th don't contain all nodes,
+ // so for missing nodes we add null NeighborArray
+ int nullsToAdd = node - graph.get(level).size();
+ for (int i = 0; i < nullsToAdd; i++) {
Review comment:
Indeed, this is not the ideal implementation, as we would need extra RAM
to store all references to null objects.
I've added a TODO to optimize RAM later.
Or would you suggest to do this optimization in this PR? We can:
1. keep only dense ordinals in the current level, and add another field to
`HnswGraph` : `List<List<Integer>> nodesByLevels` that will encode the (layer
0) node ids in each other layers.
2. When doing `getNeighbors(int level, int node)` we can do a binary search
among `nodesByLevel.get(level)` to find the index of this node on the current
level.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]