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]

Reply via email to