You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "zhaih (via GitHub)" <gi...@apache.org> on 2023/04/19 03:31:52 UTC
[GitHub] [lucene] zhaih opened a new pull request, #12235: Optimize HNSW diversity calculation
zhaih opened a new pull request, #12235:
URL: https://github.com/apache/lucene/pull/12235
### Description
Currently when we pop out the worst diverse node we go from the most distant node and calculate diversity one by one. But actually when we add the first batch of neighbours, we have already checked the diversity and rejected the non-diverse node. So the only nodes that are unchecked are only the ones that inserted by neighbours (using `insertSorted`), we should be able to only check those "unchecked" nodes but not every node.
I rely on current unit test to check the correctness but if that's not enough I'm pretty happy to write some test as well.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] benwtrent commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1546025921
@zhaih I verified your change doesn't hurt recall. Is this change good to continue working on? I tried replicating your performance improvements, but did not see that big of a change. My search time latency might be drowning out the index build latency.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] MarcusSorealheis commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "MarcusSorealheis (via GitHub)" <gi...@apache.org>.
MarcusSorealheis commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1178774555
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
As a principal, that totally makes sense. For this specific project, it makes even more sense because it's pretty complicated in some areas.
The other two files are codec files with identical logic in this section, so it probably would not pose much of a problem. Although, I'm sure others could weigh in or -1 if adamant about `nbrNbr`. Most of the time, I favor readability over anything else. That could be because I am lazy. 😛 `nbrsOfNbr` is really clear while also being few characters to type. Still, no pressure.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1522617195
The test error seems due to a flaw introduced in https://github.com/apache/lucene/pull/12169, since it seems they're anyway gonna rework on it for thread safety reason I left a comment there.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1546537128
@benwtrent I was originally waiting for https://github.com/apache/lucene/pull/12246 to be merged first so that this PR won't break their test, but seems that one is blocked somehow by other PR so I'll just fix the problem here.
I think if this time all the checks passed I'll just merge this PR
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] msokolov commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1172949798
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -29,16 +29,27 @@
* @lucene.internal
*/
public class NeighborArray {
+ static final int UNCHECKED_NODE_INIT_SIZE = 4;
private final boolean scoresDescOrder;
private int size;
float[] score;
int[] node;
+ final NeighborArray uncheckedNodes;
public NeighborArray(int maxSize, boolean descOrder) {
+ this(maxSize, descOrder, false);
+ }
+
+ public NeighborArray(int maxSize, boolean descOrder, boolean tracUncheckedNodes) {
Review Comment:
I'm finding it difficult to keep track of what these booleans mean. It's especially confusing when there are two of them. Is it possible to make this ctor (or the other one) private? Do we only call this with `tracUncheckedNodes==false` from here?
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -62,7 +73,7 @@ public void add(int newNode, float newScore) {
}
/** Add a new node to the NeighborArray into a correct sort position according to its score. */
- public void insertSorted(int newNode, float newScore) {
+ public void insertSorted(int newNode, float newScore, boolean setUncheck) {
Review Comment:
again can we simplify the API getting rid of this boolean parameter? We could eg make a private method accepting the boolean and then two public methods: `insertSortedNoTracking` and `insertSortedWithTracking`?
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1518409710
@msokolov Thanks for your feedback. Indeed the memory consumption is a concern and after I thought it more I found that it might be better to lazily sort the nodes and figure out which nodes are unchecked all at once.
In this way we still able to avoid the extra computation at the cost of 1 extra int, which I believe is more or less negligible now.
For sure I will do the KnnGraphTester (and thank you for pointing me to there, TBH I haven't done any test with KNN yet...) still to just see whether the performance gain is observable, but let me know whether the latter approach addresses your concern.
Thank you!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1174215397
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -62,7 +73,7 @@ public void add(int newNode, float newScore) {
}
/** Add a new node to the NeighborArray into a correct sort position according to its score. */
- public void insertSorted(int newNode, float newScore) {
+ public void insertSorted(int newNode, float newScore, boolean setUncheck) {
Review Comment:
yeah.. This is gone with the lazy approach as well!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1174215308
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -29,16 +29,27 @@
* @lucene.internal
*/
public class NeighborArray {
+ static final int UNCHECKED_NODE_INIT_SIZE = 4;
private final boolean scoresDescOrder;
private int size;
float[] score;
int[] node;
+ final NeighborArray uncheckedNodes;
public NeighborArray(int maxSize, boolean descOrder) {
+ this(maxSize, descOrder, false);
+ }
+
+ public NeighborArray(int maxSize, boolean descOrder, boolean tracUncheckedNodes) {
Review Comment:
This should be gone with the lazy approach
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1175733535
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
Yeah this is not quite descriptive but I'm not sure whether I can come up with a better one.. Maybe `nbrsOfNbr`? `neighborArray` is not exactly right since it is actually "the neighbor array of the neighbor" LOL
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih merged pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih merged PR #12235:
URL: https://github.com/apache/lucene/pull/12235
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1174215397
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -62,7 +73,7 @@ public void add(int newNode, float newScore) {
}
/** Add a new node to the NeighborArray into a correct sort position according to its score. */
- public void insertSorted(int newNode, float newScore) {
+ public void insertSorted(int newNode, float newScore, boolean setUncheck) {
Review Comment:
This is gone as well!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1178603598
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
I can do it for the other files because there are not many of them, however I don't usually do a text search for the whole repo to see whether the rename can be applied even to the files I haven't touched originally...
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] MarcusSorealheis commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "MarcusSorealheis (via GitHub)" <gi...@apache.org>.
MarcusSorealheis commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1175891696
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
I think `neighborArray` would be an improvement but not completely accurate. `neighborsArray` would be implicitly good, too, yet implicit is not good enough and it's not clear about the relationship with the neighbor in focus.
`nbrsOfNbr` is even more clear. I'd recommend going with your suggestion.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] MarcusSorealheis commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "MarcusSorealheis (via GitHub)" <gi...@apache.org>.
MarcusSorealheis commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1178293476
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
Is the change unneeded in the Lucene90 file if it's changed here? I was thinking we could rename `nbrNbr` wherever it is used because it is confusing.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1527034820
> Oh I see there is a precommit test failing...
Yeah I want to wait for that fix a bit before I merge this one... Since anyway this won't make into Lucene 9.6 LOL
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] msokolov commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1179184450
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -59,23 +61,72 @@ public void add(int newNode, float newScore) {
node[size] = newNode;
score[size] = newScore;
++size;
+ ++sortedNodeSize;
}
- /** Add a new node to the NeighborArray into a correct sort position according to its score. */
- public void insertSorted(int newNode, float newScore) {
+ /** Add node and score but do not insert as sorted */
+ public void addOutOfOrder(int newNode, float newScore) {
if (size == node.length) {
node = ArrayUtil.grow(node);
score = ArrayUtil.growExact(score, node.length);
}
+ node[size] = newNode;
+ score[size] = newScore;
+ size++;
+ }
+
+ /**
+ * Sort the array according to scores, and return the sorted indexes of previous unsorted nodes
+ * (unchecked nodes)
+ *
+ * @return indexes of newly sorted (unchecked) nodes, in ascending order, or null if the array is
+ * already fully sorted
+ */
+ public int[] sort() {
Review Comment:
LGTM. After reading I think I see what's going on. The name is deceptively simple; I wonder if it shouldn't hint that there is something tricky going on in here? Like `sortAndReturnPreviouslyUnsorted()` :) but it's fine to leave as is - the javadoc anyway explains it
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1519337576
I ran the `KnnGraphTester` and pasted the result to the description, basically when max-conn is low (there's high possiblility of popping out a node) the improvement seems to be obvious (2-5% on indexing time), when max-conn is high then the indexing time is similar or only slightly better, which is also expected.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1179964872
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java:
##########
@@ -59,23 +61,72 @@ public void add(int newNode, float newScore) {
node[size] = newNode;
score[size] = newScore;
++size;
+ ++sortedNodeSize;
}
- /** Add a new node to the NeighborArray into a correct sort position according to its score. */
- public void insertSorted(int newNode, float newScore) {
+ /** Add node and score but do not insert as sorted */
+ public void addOutOfOrder(int newNode, float newScore) {
if (size == node.length) {
node = ArrayUtil.grow(node);
score = ArrayUtil.growExact(score, node.length);
}
+ node[size] = newNode;
+ score[size] = newScore;
+ size++;
+ }
+
+ /**
+ * Sort the array according to scores, and return the sorted indexes of previous unsorted nodes
+ * (unchecked nodes)
+ *
+ * @return indexes of newly sorted (unchecked) nodes, in ascending order, or null if the array is
+ * already fully sorted
+ */
+ public int[] sort() {
Review Comment:
Haha I'll just leave it as is. It claims itself is "sort" and it does the sort, but just return something different :)
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] msokolov commented on pull request #12235: Optimize HNSW diversity calculation
Posted by "msokolov (via GitHub)" <gi...@apache.org>.
msokolov commented on PR #12235:
URL: https://github.com/apache/lucene/pull/12235#issuecomment-1520074992
I see; well there seems like some benefit. Also, the impact is going to vary depending on the nature of the data. I guess we'd expect that vectors with a high degree of "clustering" would tend to have more ejections due to diversity checks.Let me take one more pass and see if there's any more polishing to do, otherwise it seems good to me.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "zhaih (via GitHub)" <gi...@apache.org>.
zhaih commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1176047399
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
Sure, changed!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] MarcusSorealheis commented on a diff in pull request #12235: Optimize HNSW diversity calculation
Posted by "MarcusSorealheis (via GitHub)" <gi...@apache.org>.
MarcusSorealheis commented on code in PR #12235:
URL: https://github.com/apache/lucene/pull/12235#discussion_r1175657275
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphBuilder.java:
##########
@@ -306,7 +308,7 @@ private void addDiverseNeighbors(int level, int node, NeighborQueue candidates)
for (int i = 0; i < size; i++) {
int nbr = neighbors.node[i];
NeighborArray nbrNbr = hnsw.getNeighbors(level, nbr);
- nbrNbr.insertSorted(node, neighbors.score[i]);
+ nbrNbr.addOutOfOrder(node, neighbors.score[i]);
Review Comment:
Nit: I know we use `nbrNbr` in a [few more places](https://github.com/apache/lucene/blob/4deb0003c425bfaff3923661512c44a315172854/lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/Lucene90HnswGraphBuilder.java#L186), but as you have reminded me, the nondescript names could make it more difficult for others to understand the code and participate.
Is there another way to express this to make it easier for people to read/scan? `neighborArray` to be most explicit, `candidateNeighbors` or something else? You would only need to change two other files to preserve consistency if you elected to move from `nbrNbr`
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org