0z5a opened a new pull request, #581:
URL: https://github.com/apache/datasketches-cpp/pull/581

   `ebpps_sketch::internal_merge()` computes `new_wt_max = max(wt_max_, 
sk.wt_max_)` and uses it for every rho step of the merge, but never stores it. 
After the merge, `wt_max_` is still the value of whichever sketch ends up as 
the target, so if the heavier item came from the other sketch the sketch 
forgets it.
   
   The next `update()` then computes `rho = min(1 / wt_max_, k / cum_wt)` with 
the stale maximum, so rho can go up. `ebpps_sample::downsample()` ignores 
ratios at or above 1, so the items already in the sample are not scaled up to 
match, and from then on the sample is no longer proportional to weight. The 
stale value is also written by `serialize()`, so a deserialized sketch carries 
it forward.
   
   Example with k = 10: one sketch gets 1000 items of weight 1, another gets 
one item of weight 500, and the second is merged into the first. Then 2000 more 
items of weight 1 are added. A single sketch fed the same 3001 items always 
keeps the weight-500 item (its inclusion probability is min(1, rho * 500) = 1) 
and keeps every weight-1 item with probability 0.002. In one set of 2000 runs 
of the merged version, the weight-500 item was kept in 44% of the runs, the 
weight-1 items from before the merge were kept at a rate of 0.00086 each, and 
the ones added after the merge at 0.00285.
   
   The same thing happens when the heavy item is in the target sketch and the 
other sketch has the larger cumulative weight, because the two sketches are 
swapped before `internal_merge()` runs. Both the lvalue and rvalue overloads 
are affected.
   
   The fix stores `new_wt_max` together with the final cumulative weight and n. 
Since every `merge()` overload goes through `internal_merge()`, this one line 
covers all of them.
   
   The new test merges a weight-500 item with 1000 weight-1 items in all four 
ways (lvalue and rvalue, with and without the swap), adds one more weight-1 
item, and checks C against a single sketch fed the same items. C depends only 
on the sequence of rho values and not on the random choices, so the check is 
deterministic. Before the fix C is 3.00666 in all four cases. The single-sketch 
value, and the value after the fix, is 3.002.
   
   The Java implementation (`EbppsItemsSketch.internalMerge`) has the same 
omission. There are no cross-language EBPPS fixtures, so no generated files 
change.
   
   This change was drafted with Claude Code (claude-opus-5-5); the test results 
above are from the runs described.
   


-- 
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]

Reply via email to