You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by jm...@apache.org on 2025/01/10 21:58:17 UTC
(datasketches-python) branch tdigest_docs created (now d2d1039)
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a change to branch tdigest_docs
in repository https://gitbox.apache.org/repos/asf/datasketches-python.git
at d2d1039 Add get_PMF and get_CDF to t-digest, add t-digest docs, update tdigest merge to const input
This branch includes the following new commits:
new d2d1039 Add get_PMF and get_CDF to t-digest, add t-digest docs, update tdigest merge to const input
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
(datasketches-python) 01/01: Add get_PMF and get_CDF to t-digest, add t-digest docs, update tdigest merge to const input
Posted by jm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch tdigest_docs
in repository https://gitbox.apache.org/repos/asf/datasketches-python.git
commit d2d103983bc4a08b4abe4fe2767b06fa2b8fb519
Author: Jon Malkin <78...@users.noreply.github.com>
AuthorDate: Fri Jan 10 13:57:58 2025 -0800
Add get_PMF and get_CDF to t-digest, add t-digest docs, update tdigest merge to const input
---
CMakeLists.txt | 2 +-
NOTICE | 4 ++--
README.md | 5 +++-
docs/source/quantiles/index.rst | 14 +++++++----
docs/source/quantiles/kll.rst | 5 ----
docs/source/quantiles/tdigest.rst | 50 +++++++++++++++++++++++++++++++++++++++
src/tdigest_wrapper.cpp | 29 ++++++++++++++++++++++-
tests/tdigest_test.py | 17 +++++++++++++
8 files changed, 111 insertions(+), 15 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4e9ba96..2e74346 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -117,7 +117,7 @@ cmake_policy(SET CMP0097 NEW)
include(ExternalProject)
ExternalProject_Add(datasketches
GIT_REPOSITORY https://github.com/apache/datasketches-cpp.git
- GIT_TAG 5.1.0
+ GIT_TAG 5.2.0
GIT_SHALLOW true
GIT_SUBMODULES ""
INSTALL_DIR /tmp/datasketches
diff --git a/NOTICE b/NOTICE
index 1305168..1668e07 100644
--- a/NOTICE
+++ b/NOTICE
@@ -1,9 +1,9 @@
Apache DataSketches Python
-Copyright 2024 The Apache Software Foundation
+Copyright 2025 The Apache Software Foundation
Copyright 2015-2018 Yahoo Inc.
Copyright 2019-2020 Verizon Media
-Copyright 2021 Yahoo Inc.
+Copyright 2021- Yahoo Inc.
This product includes software developed at
The Apache Software Foundation (http://www.apache.org/).
diff --git a/README.md b/README.md
index 2641de8..9961496 100644
--- a/README.md
+++ b/README.md
@@ -75,10 +75,13 @@ The unit tests are mostly structured in a tutorial style and can be used as a re
- `vector_of_kll_floats_sketches`
- Kolmogorov-Smirnov Test
- `ks_test` applied to a pair of matched-type Absolute Error quantiles sketches
-- Density
+- Kernel Density
- `density_sketch`
- Count-min sketch
- `count_min_sketch`
+- t-digest
+ - tdigest_float
+ - tdigest_double
## Known Differences from C++
diff --git a/docs/source/quantiles/index.rst b/docs/source/quantiles/index.rst
index b1928f6..bf53ea3 100644
--- a/docs/source/quantiles/index.rst
+++ b/docs/source/quantiles/index.rst
@@ -10,17 +10,21 @@ in the stream.
These sketches may be used to compute approximate histograms, Probability Mass Functions (PMFs), or
Cumulative Distribution Functions (CDFs).
-The library provides three types of quantiles sketches, each of which has generic items as well as versions
-specific to a given numeric type (e.g. integer or floating point values). All three types provide error
-bounds on rank estimation with proven probabilistic error distributions.
+The library provides four types of quantiles sketches, three of which have generic items as well as versions
+specific to a given numeric type (e.g. integer or floating point values). Those three types provide error
+bounds on rank estimation with proven probabilistic error distributions. t-digest is a heuristic-based sketch
+that works only on numeric data, and while the error properties are not guaranteed, the sketch typically
+does a good job with small storage.
- * KLL: Provides uniform rank estimation error over the entire range
+ * KLL: Provides uniform rank estimation error over the entire range.
* REQ: Provides relative rank error estimates, which decreases approaching either the high or low end values.
+ * t-digest: Relative rank error estimates, heuristic-based without guarantees but quite compact with generally very good error properties.
* Classic quantiles: Largely deprecated in favor of KLL, also provides uniform rank estimation error. Included largely for backwards compatibility with historic data.
.. toctree::
:maxdepth: 1
-
+
kll
req
+ tdigest
quantiles_depr
\ No newline at end of file
diff --git a/docs/source/quantiles/kll.rst b/docs/source/quantiles/kll.rst
index 0e54b44..ab7f0c4 100644
--- a/docs/source/quantiles/kll.rst
+++ b/docs/source/quantiles/kll.rst
@@ -14,10 +14,6 @@ The analysis is obtained using `get_quantile()` function or the
inverse functions `get_rank()`, `get_pmf()` (Probability Mass Function), and `get_cdf()`
(Cumulative Distribution Function).
-As of May 2020, this implementation produces serialized sketches which are binary-compatible
-with the equivalent Java implementation only when template parameter `T = float`
-(32-bit single precision values).
-
Given an input stream of `N` items, the `natural rank` of any specific
item is defined as its index `(1 to N)` in inclusive mode
or `(0 to N-1)` in exclusive mode
@@ -168,4 +164,3 @@ Additionally, the interval may be quite large for certain distributions.
.. rubric:: Non-static Methods:
.. automethod:: __init__
-
diff --git a/docs/source/quantiles/tdigest.rst b/docs/source/quantiles/tdigest.rst
new file mode 100644
index 0000000..1af4a9e
--- /dev/null
+++ b/docs/source/quantiles/tdigest.rst
@@ -0,0 +1,50 @@
+t-digest
+--------
+
+.. currentmodule:: datasketches
+
+The implementation in this library is based on the MergingDigest described in
+`Computing Extremely Accurate Quantiles Using t-Digests <https://arxiv.org/abs/1902.04023>`_ by Ted Dunning and Otmar Ertl.
+
+The implementation in this library has a few differences from the reference implementation associated with that paper:
+
+* Merge does not modify the input
+* Derialization similar to other sketches in this library, although reading the reference implementation format is supported
+
+Unlike all other algorithms in the library, t-digest is empirical and has no mathematical basis for estimating its error
+and its results are dependent on the input data. However, for many common data distributions, it can produce excellent results.
+t-digest also operates only on numeric data and, unlike the the quantiles family algorithms in the library which return quantile
+approximations from the input domain, t-digest interpolates values and will hold and return data points not seen in the input.
+
+The closest alternative to t-digest in this library is REQ sketch. It prioritizes one chosen side of the rank domain:
+either low rank accuracy or high rank accuracy. t-digest (in this implementation) prioritizes both ends of the rank domain
+and has lower accuracy towards the middle of the rank domain (median).
+
+Measurements show that t-digest is slightly biased (tends to underestimate low ranks and overestimate high ranks), while still
+doing very well close to the extremes. The effect seems to be more pronounced with more input values.
+
+.. autoclass:: tdigest_float
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
+
+.. autoclass:: tdigest_double
+ :members:
+ :undoc-members:
+ :exclude-members: deserialize
+
+ .. rubric:: Static Methods:
+
+ .. automethod:: deserialize
+
+ .. rubric:: Non-static Methods:
+
+ .. automethod:: __init__
diff --git a/src/tdigest_wrapper.cpp b/src/tdigest_wrapper.cpp
index 059ee1d..43248fb 100644
--- a/src/tdigest_wrapper.cpp
+++ b/src/tdigest_wrapper.cpp
@@ -24,6 +24,7 @@
#include <nanobind/nanobind.h>
#include <nanobind/make_iterator.h>
#include <nanobind/stl/string.h>
+#include <nanobind/stl/vector.h>
#include <nanobind/ndarray.h>
#include "tdigest.hpp"
@@ -44,7 +45,7 @@ void bind_tdigest(nb::module_ &m, const char* name) {
.def("__copy__", [](const tdigest<T>& sk) { return tdigest<T>(sk); })
.def("update", (void(tdigest<T>::*)(T)) &tdigest<T>::update, nb::arg("item"),
"Updates the sketch with the given value")
- .def("merge", (void(tdigest<T>::*)(tdigest<T>&)) &tdigest<T>::merge, nb::arg("sketch"),
+ .def("merge", (void(tdigest<T>::*)(const tdigest<T>&)) &tdigest<T>::merge, nb::arg("sketch"),
"Merges the provided sketch into this one")
.def("__str__", [](const tdigest<T>& sk) { return sk.to_string(); },
"Produces a string summary of the sketch")
@@ -71,6 +72,32 @@ void bind_tdigest(nb::module_ &m, const char* name) {
.def("get_serialized_size_bytes", &tdigest<T>::get_serialized_size_bytes,
nb::arg("with_buffer")=false,
"Returns the size of the serialized sketch, in bytes")
+ .def(
+ "get_pmf",
+ [](const tdigest<T>& sk, const std::vector<T>& split_points) {
+ return sk.get_PMF(split_points.data(), split_points.size());
+ },
+ nb::arg("split_points"),
+ "Returns an approximation to the Probability Mass Function (PMF) of the input stream "
+ "given a set of split points (values).\n"
+ "If the sketch is empty this returns an empty vector.\n"
+ "split_points is an array of m unique, monotonically increasing float values "
+ "that divide the real number line into m+1 consecutive disjoint intervals.\n"
+ "It is not necessary to include either the min or max values in these split points."
+ )
+ .def(
+ "get_cdf",
+ [](const tdigest<T>& sk, const std::vector<T>& split_points) {
+ return sk.get_CDF(split_points.data(), split_points.size());
+ },
+ nb::arg("split_points"),
+ "Returns an approximation to the Cumulative Distribution Function (CDF), which is the "
+ "cumulative analog of the PMF, of the input stream given a set of split points (values).\n"
+ "If the sketch is empty this returns an empty vector.\n"
+ "split_points is an array of m unique, monotonically increasing float values "
+ "that divide the real number line into m+1 consecutive disjoint intervals.\n"
+ "It is not necessary to include either the min or max values in these split points."
+ )
;
add_serialization<T>(tdigest_class);
diff --git a/tests/tdigest_test.py b/tests/tdigest_test.py
index fab32c4..de36f69 100644
--- a/tests/tdigest_test.py
+++ b/tests/tdigest_test.py
@@ -50,6 +50,15 @@ class TdigestTest(unittest.TestCase):
self.assertFalse(td.is_empty())
self.assertEqual(td.get_total_weight(), n)
+ # we can get the PMF and CDF
+ pmf = td.get_pmf([-0.5, 0.0, 0.5])
+ self.assertEqual(len(pmf), 4)
+ self.assertAlmostEqual(sum(pmf), 1.0)
+
+ cdf = td.get_cdf([0.0])
+ self.assertEqual(len(cdf), 2)
+ self.assertAlmostEqual(cdf[0], 0.5, delta = 0.05)
+
# we can define a new tdiget with a different distribution, then merge them
td2 = tdigest_double()
td2.update(np.random.normal(loc=2.0, size=n))
@@ -89,6 +98,14 @@ class TdigestTest(unittest.TestCase):
self.assertFalse(td.is_empty())
self.assertEqual(td.get_total_weight(), n)
+ pmf = td.get_pmf([-0.5, 0.0, 0.5])
+ self.assertEqual(len(pmf), 4)
+ self.assertAlmostEqual(sum(pmf), 1.0)
+
+ cdf = td.get_cdf([0.0])
+ self.assertEqual(len(cdf), 2)
+ self.assertAlmostEqual(cdf[0], 0.5, delta = 0.05)
+
td2 = tdigest_float()
td2.update(np.random.normal(loc=2.0, size=n))
td.merge(td2)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org