stojkomilos opened a new pull request, #567: URL: https://github.com/apache/datasketches-cpp/pull/567
## What changed `kll_sketch` and `quantiles_sketch` keep the exact min and max of the stream. But `get_quantile(0)` and `get_quantile(1)` read only the retained items, and compaction can drop the min and max from them. Then ranks 0 and 1 give a retained item, not the exact min and max: ```cpp kll_sketch<float> sketch(8); sketch.update(0); sketch.update(999); for (int i = 1; i < 999; ++i) sketch.update(i); sketch.get_min_item(); // 0 sketch.get_quantile(0); // 23 (changes from run to run) sketch.get_max_item(); // 999 sketch.get_quantile(1); // 998 ``` Since 6.0.0, datasketches-java returns the exact min and max here (apache/datasketches-java#547, `IncludeMinMax`). Its sorted views add the min and max back when the retained items do not hold them. So for the same data, the two libraries give different answers at ranks 0 and 1. We found this when we ran the same queries on engines that use each library. This PR ports that step to C++: - New `quantiles_sorted_view::include_min_max()`, with the same arithmetic as Java. A missing min goes first, with cumulative weight 1. A missing max goes last, and the entry before it gives 1 of its weight to the max. The total weight does not change. - `kll_sketch::get_sorted_view()` and `quantiles_sketch::get_sorted_view()` call it. So `get_quantile()`, `get_rank()`, `get_PMF()`, `get_CDF()` and the sorted view iterator all see the min and max, as in Java. Behavior change: only ranks within 1/n of 0 or 1 give a different quantile, and a rank changes by at most 1/n. For example, the inclusive rank of a dropped min is now 1/n, not 0. These are the values that Java returns for the same data. REQ does not change. Its `get_rank()` reads the compactors, not the sorted view. If only the view has the min and max, `get_rank()` and `get_sorted_view().get_rank()` disagree, and the `get_rank equivalence` test fails. Java REQ also adds the min and max. I can send a follow-up that moves REQ `get_rank()` to the sorted view. For non-arithmetic types, the view now also points to the min and max in the sketch object, not only to its item buffer. So a move of the sketch now also makes an earlier view invalid. ## How tested **Added** `quantiles_sorted_view_test` (3 tests), with the data of the Java `IncludeMinMaxTest`: - Edge cases (3 separate tests): both missing, both retained, and one retained item. Each checks the entries and their cumulative weights. Two also check the quantiles at ranks 0 and 1. `kll_sketch_test` and `quantiles_sketch_test` (3 sections): each builds 100 sketches with k = 8 and adds the min and max first, so compaction drops them. - Sketches (KLL float, KLL string, quantiles float = 3 tests): ranks 0 and 1 give the exact min and max, inclusive and exclusive. The float tests also check the Java ranks of a dropped min and max. Each test requires at least one sketch that dropped them. **Test strength**: with `include_min_max()` changed to do nothing, 5 of the 6 tests fail. The "both retained" test passes by design. This pull request and its description were written by Isaac. -- 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]
