You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2020/12/19 00:27:21 UTC

[incubator-datasketches-cpp] branch req_sketch updated: implemented bounds

This is an automated email from the ASF dual-hosted git repository.

alsay pushed a commit to branch req_sketch
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git


The following commit(s) were added to refs/heads/req_sketch by this push:
     new a57e210  implemented bounds
a57e210 is described below

commit a57e21039442884c2bb693a9225a01747c318d4f
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Fri Dec 18 16:27:08 2020 -0800

    implemented bounds
---
 req/include/req_sketch.hpp      | 41 +++++++++++++++++++++++++++++++
 req/include/req_sketch_impl.hpp | 53 +++++++++++++++++++++++++++++++++++++++++
 req/test/req_sketch_test.cpp    |  6 +++++
 3 files changed, 100 insertions(+)

diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index 4f82910..1e61ee8 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -50,6 +50,12 @@ public:
   req_sketch& operator=(req_sketch&& other);
 
   /**
+   * Returns configured parameter K
+   * @return parameter K
+   */
+  uint16_t get_k() const;
+
+  /**
    * Returns true if this sketch is empty.
    * @return empty flag
    */
@@ -172,6 +178,34 @@ public:
   vector_const_t_ptr get_quantiles(const double* ranks, uint32_t size) const;
 
   /**
+   * Returns an approximate lower bound of the given noramalized rank.
+   * @param rank the given rank, a value between 0 and 1.0.
+   * @param num_std_dev the number of standard deviations. Must be 1, 2, or 3.
+   * @return an approximate lower bound rank.
+   */
+  double get_rank_lower_bound(double rank, uint8_t num_std_dev) const;
+
+  /**
+   * Returns an approximate upper bound of the given noramalized rank.
+   * @param rank the given rank, a value between 0 and 1.0.
+   * @param num_std_dev the number of standard deviations. Must be 1, 2, or 3.
+   * @return an approximate upper bound rank.
+   */
+  double get_rank_upper_bound(double rank, uint8_t num_std_dev) const;
+
+  /**
+   * Returns an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).
+   * Derived from Lemma 12 in https://arxiv.org/abs/2004.01668v2, but the constant factors were
+   * modified based on empirical measurements.
+   *
+   * @param k the given value of k
+   * @param rank the given normalized rank, a number in [0,1].
+   * @param n an estimate of the total number of items submitted to the sketch.
+   * @return an a priori estimate of relative standard error (RSE, expressed as a number in [0,1]).
+   */
+  static double get_RSE(uint16_t k, double rank, uint64_t n);
+
+  /**
    * Computes size needed to serialize the current state of the sketch.
    * This version is for fixed-size arithmetic types (integral and floating point).
    * @return size in bytes needed to serialize this sketch
@@ -243,12 +277,19 @@ private:
   static const size_t PREAMBLE_SIZE_BYTES = 8;
   enum flags { RESERVED1, RESERVED2, IS_EMPTY, IS_HIGH_RANK, RAW_ITEMS, IS_LEVEL_ZERO_SORTED };
 
+  static constexpr double FIXED_RSE_FACTOR = 0.06;
+  static double relative_rse_factor();
+
   uint8_t get_num_levels() const;
   void grow();
   void update_max_nom_size();
   void update_num_retained();
   void compress();
 
+  static double get_rank_lb(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n);
+  static double get_rank_ub(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n);
+  static bool is_exact_rank(uint16_t k, uint8_t num_levels, double rank, uint64_t n);
+
   using QuantileCalculator = req_quantile_calculator<T, Comparator, Allocator>;
   using AllocCalc = typename std::allocator_traits<Allocator>::template rebind_alloc<QuantileCalculator>;
   class calculator_deleter;
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index 44dbd19..cf1acb3 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -109,6 +109,11 @@ req_sketch<T, H, C, S, A>& req_sketch<T, H, C, S, A>::operator=(req_sketch&& oth
 }
 
 template<typename T, bool H, typename C, typename S, typename A>
+uint16_t req_sketch<T, H, C, S, A>::get_k() const {
+  return k_;
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
 bool req_sketch<T, H, C, S, A>::is_empty() const {
   return n_ == 0;
 }
@@ -283,6 +288,54 @@ auto req_sketch<T, H, C, S, A>::get_quantile_calculator() const -> QuantileCalcu
   return quantile_calculator;
 }
 
+template<typename T, bool H, typename C, typename S, typename A>
+double req_sketch<T, H, C, S, A>::get_rank_lower_bound(double rank, uint8_t num_std_dev) const {
+  return get_rank_lb(get_k(), get_num_levels(), rank, num_std_dev, get_n());
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+double req_sketch<T, H, C, S, A>::get_rank_upper_bound(double rank, uint8_t num_std_dev) const {
+  return get_rank_ub(get_k(), get_num_levels(), rank, num_std_dev, get_n());
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+double req_sketch<T, H, C, S, A>::get_RSE(uint16_t k, double rank, uint64_t n) {
+  return get_rank_lb(k, 2, rank, 1, n);
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+double req_sketch<T, H, C, S, A>::get_rank_lb(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n) {
+  if (is_exact_rank(k, num_levels, rank, n)) return rank;
+  const double relative = relative_rse_factor() / k * (H ? 1.0 - rank : rank);
+  const double fixed = FIXED_RSE_FACTOR / k;
+  const double lb_rel = rank - num_std_dev * relative;
+  const double lb_fix = rank - num_std_dev * fixed;
+  return std::max(lb_rel, lb_fix);
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+double req_sketch<T, H, C, S, A>::get_rank_ub(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n) {
+  if (is_exact_rank(k, num_levels, rank, n)) return rank;
+  const double relative = relative_rse_factor() / k * (H ? 1.0 - rank : rank);
+  const double fixed = FIXED_RSE_FACTOR / k;
+  const double ub_rel = rank + num_std_dev * relative;
+  const double ub_fix = rank + num_std_dev * fixed;
+  return std::min(ub_rel, ub_fix);
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+bool req_sketch<T, H, C, S, A>::is_exact_rank(uint16_t k, uint8_t num_levels, double rank, uint64_t n) {
+  const unsigned base_cap = k * req_constants::INIT_NUM_SECTIONS;
+  if (num_levels == 1 || n <= base_cap) return true;
+  const double exact_rank_thresh = static_cast<double>(base_cap) / n;
+  return (H && rank >= 1.0 - exact_rank_thresh) || (!H && rank <= exact_rank_thresh);
+}
+
+template<typename T, bool H, typename C, typename S, typename A>
+double req_sketch<T, H, C, S, A>::relative_rse_factor() {
+  return sqrt(0.0512 / req_constants::INIT_NUM_SECTIONS);
+}
+
 // implementation for fixed-size arithmetic types (integral and floating point)
 template<typename T, bool H, typename C, typename S, typename A>
 template<typename TT, typename std::enable_if<std::is_arithmetic<TT>::value, int>::type>
diff --git a/req/test/req_sketch_test.cpp b/req/test/req_sketch_test.cpp
index 9706310..45de223 100755
--- a/req/test/req_sketch_test.cpp
+++ b/req/test/req_sketch_test.cpp
@@ -35,6 +35,7 @@ const std::string input_path = "test/";
 
 TEST_CASE("req sketch: empty", "[req_sketch]") {
   req_sketch<float, true> sketch(12);
+  REQUIRE(sketch.get_k() == 12);
   REQUIRE(sketch.is_empty());
   REQUIRE_FALSE(sketch.is_estimation_mode());
   REQUIRE(sketch.get_n() == 0);
@@ -145,6 +146,9 @@ TEST_CASE("req sketch: exact mode", "[req_sketch]") {
   REQUIRE(pmf[1] == Approx(0.4).margin(1e-8));
   REQUIRE(pmf[2] == Approx(0.3).margin(1e-8));
   REQUIRE(pmf[3] == Approx(0.2).margin(1e-8));
+
+  REQUIRE(sketch.get_rank_lower_bound(0.5, 1) == 0.5);
+  REQUIRE(sketch.get_rank_upper_bound(0.5, 1) == 0.5);
 }
 
 TEST_CASE("req sketch: estimation mode", "[req_sketch]") {
@@ -162,6 +166,8 @@ TEST_CASE("req sketch: estimation mode", "[req_sketch]") {
   REQUIRE(sketch.get_rank(n - 1) == Approx(1).margin(0.01));
   REQUIRE(sketch.get_min_value() == 0);
   REQUIRE(sketch.get_max_value() == n - 1);
+  REQUIRE(sketch.get_rank_lower_bound(0.5, 1) < 0.5);
+  REQUIRE(sketch.get_rank_upper_bound(0.5, 1) > 0.5);
 }
 
 TEST_CASE("req sketch: stream serialize-deserialize empty", "[req_sketch]") {


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org