You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "jmalkin (via GitHub)" <gi...@apache.org> on 2025/01/10 22:06:45 UTC
[PR] t-digest changes [datasketches-python]
jmalkin opened a new pull request, #58:
URL: https://github.com/apache/datasketches-python/pull/58
* add get_PMF and get_CDF to t-digest wrapper
* add t-digest docs
* update tdigestt merge to const input
I updated NOTICE and removed some now-outdated stuff from KLL docs, too.
The CI build will fail until the c++ 5.2.0 tag is live. We need to hold off on this PR until that's ready.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] t-digest changes [datasketches-python]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on code in PR #58:
URL: https://github.com/apache/datasketches-python/pull/58#discussion_r1917461209
##########
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
Review Comment:
double "the"
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] t-digest changes [datasketches-python]
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin merged PR #58:
URL: https://github.com/apache/datasketches-python/pull/58
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] t-digest changes [datasketches-python]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on code in PR #58:
URL: https://github.com/apache/datasketches-python/pull/58#discussion_r1917465351
##########
tests/tdigest_test.py:
##########
@@ -50,6 +50,15 @@ def test_tdigest_double_example(self):
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
Review Comment:
tdiget
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] t-digest changes [datasketches-python]
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on code in PR #58:
URL: https://github.com/apache/datasketches-python/pull/58#discussion_r1917473640
##########
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.
Review Comment:
...(add) with large enough data.
##########
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.
Review Comment:
...(add) with large enough data.
##########
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.
Review Comment:
...(add) and large enough input data.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] t-digest changes [datasketches-python]
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on PR #58:
URL: https://github.com/apache/datasketches-python/pull/58#issuecomment-2594227748
Added a link to satisfy the requested change. Will merge.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org