mayya-sharipova opened a new pull request, #16438:
URL: https://github.com/apache/lucene/pull/16438
Backport of #16435 to `branch_10x` (cherry-pick of 5fa57e79659, applied
cleanly).
`UpdateGraphsUtils#computeJoinSet` asked for a coverage of 2 for every node
with a
degree below 9, including nodes with a degree of 1. Such a node can be
covered at most
once, since only its neighbours can cover it, so the coverage was
unsatisfiable and the
node always ended up in the join set itself.
On hub-and-spoke shaped graphs, which HNSW produces for 1-dimensional or
heavily
duplicated vectors, almost all nodes have a degree of 1, so the join set
degenerated to
the whole graph and merging lost all of its savings. The fix clamps the
requested
coverage by the node's degree.
`Math.min(k, degree)` differs from `k` only when `degree < 2`, as `k` is 2
for any
`degree < 9`, so join sets on graphs where every node has a degree of 2 or
more are
unchanged.
The CHANGES entry is under 10.6.0, matching #16435.
Fixes #16251
Testing on this branch (JDK 24):
- the seeds reported in #16251 (`1A7B4702F1314EA5`, `8B08865AA8BAB759`) and
in #14396
(`2D6CB1CDD2EC7901`) pass for both
`TestHnswFloatVectorGraph.testBuildingJoinSet` and
`TestHnswByteVectorGraph.testBuildingJoinSet`
- `org.apache.lucene.util.hnsw.*` with `-Ptests.iters=20`: 1760 tests pass
--
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]
