You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "benwtrent (via GitHub)" <gi...@apache.org> on 2025/03/28 11:59:40 UTC
[PR] For hnsw merger, do not pop from empty heap [lucene]
benwtrent opened a new pull request, #14420:
URL: https://github.com/apache/lucene/pull/14420
It seems there are edge cases when the heap is empty. This prevents us from attempting to pop from an empty heap.
This bug fix should go into 10.2 to make the 10.2.0 release.
closes: https://github.com/apache/lucene/issues/14407
--
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
Re: [PR] For hnsw merger, do not pop from empty heap [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14420:
URL: https://github.com/apache/lucene/pull/14420#issuecomment-2761161246
//cc @iverase as you are handling the 10.2 release.
--
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
Re: [PR] For hnsw merger, do not pop from empty heap [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #14420:
URL: https://github.com/apache/lucene/pull/14420#issuecomment-2761394895
> Does this case actually only happen when docs are reordered, or is it a general edge case that we happened to find on a test run when docs happened to be reordered?
I think its a general case. BP exposed it.
My concern, and waiting for @mayya-sharipova to clarify, is that do we want to return the set if our heap got exhausted, or do we consider it "incomplete" and return an empty set instead.
--
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
Re: [PR] For hnsw merger, do not pop from empty heap [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent merged PR #14420:
URL: https://github.com/apache/lucene/pull/14420
--
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
Re: [PR] For hnsw merger, do not pop from empty heap [lucene]
Posted by "mayya-sharipova (via GitHub)" <gi...@apache.org>.
mayya-sharipova commented on PR #14420:
URL: https://github.com/apache/lucene/pull/14420#issuecomment-2761615009
@benwtrent Please go ahead with a fix. Confirmed with @tveasey, algorithm's author.
But we also look further into it. In this particular test, graphs are unusual (small graphs with 65, 73 connections).
--
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
Re: [PR] For hnsw merger, do not pop from empty heap [lucene]
Posted by "tveasey (via GitHub)" <gi...@apache.org>.
tveasey commented on PR #14420:
URL: https://github.com/apache/lucene/pull/14420#issuecomment-2761706401
I discussed this a bit with Mayya.
So the underlying issue is how we account for the gain for degree 1 vertices. We say that the gain contribution from any vertex is at least 2, i.e. $\max\left(2, \frac{|N_s(v)|}{4}\right)$. This forces us to insert degree 1 vertices which was intentional. The problem is we can get at most +1 contribution from them to $g_{tot}$. Mayya tried it and when we correct the gain to $\min\left(\max\left(2, \frac{|N_s(v)|}{4}\right), |N_s(v)|\right)$ we terminate before exhausting the heap, as expected.
Arguably this is slightly more conceptually correct. However, it represents a change in behaviour and invalidates the testing Mayya's done. The current behaviour increases the relative size of $J$ for graphs with many degree one vertices. This seems conceptually ok. In the case the heap is exhausted we've just picked $J = V$ the set of all vertices and reverted to the original merge procedure which is clearly harmless. However, this is going to be an extreme edge case since we normally only have a small fraction of degree one vertices and we'll nearly always terminate on $g_{tot}<g_{exit}$.
Therefore, my vote is to just go with Ben's fix and leave the $g_{tot}$ calculation as is.
--
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
Re: [PR] For hnsw merger, do not pop from empty heap [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #14420:
URL: https://github.com/apache/lucene/pull/14420#issuecomment-2761367741
Does this case actually only happen when docs are reordered, or is it a general edge case that we happened to find on a test run when docs happened to be reordered?
--
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