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