You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2025/12/23 01:41:55 UTC

(datasketches-website) branch master updated: Update KLL Accuracy & Size document.

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

leerho pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/datasketches-website.git


The following commit(s) were added to refs/heads/master by this push:
     new f094a9a6 Update KLL Accuracy & Size document.
f094a9a6 is described below

commit f094a9a64dd0ad0e614e95c2d479bef0b53aa9e0
Author: Lee Rhodes <le...@gmail.com>
AuthorDate: Mon Dec 22 17:41:43 2025 -0800

    Update KLL Accuracy & Size document.
---
 docs/KLL/KLLAccuracyAndSize.md                |  13 ++++++++++++-
 docs/img/kll/KllGrowthPath_Floats&Doubles.png | Bin 0 -> 83936 bytes
 docs/img/kll/NormalizedGrowth_1B_K200.png     | Bin 0 -> 523584 bytes
 3 files changed, 12 insertions(+), 1 deletion(-)

diff --git a/docs/KLL/KLLAccuracyAndSize.md b/docs/KLL/KLLAccuracyAndSize.md
index acbebfd7..a979cae4 100644
--- a/docs/KLL/KLLAccuracyAndSize.md
+++ b/docs/KLL/KLLAccuracyAndSize.md
@@ -19,7 +19,7 @@ layout: doc_page
     specific language governing permissions and limitations
     under the License.
 -->
-# KLL Sketch Accuracy and Size
+# KLL Sketch Accuracy and Size Vs K and N
 
 The accuracy of the KLL quantile sketch is a function of the configured <i>K</i>, which also affects the overall size of the sketch (default K = 200).
 
@@ -115,3 +115,14 @@ The approximate rank error values listed in the second row of the header in the
 | 4,294,967,296      | 2,088  | 2,584 | 3,604 | 5,832 | 10,412 | 19,848 | 38,868 |
 | 8,589,934,592      | 2,164  | 2,636 | 3,648 | 5,860 | 10,504 | 19,948 | 38,968 |
 | 17,179,869,184     | 2,240  | 2,728 | 3,740 | 5,952 | 10,564 | 19,984 | 39,036 |
+
+# KLL Sketch Typical Growth Path: Size vs N
+The following graph illustrates the typical size of KLL Floats and KLL Doubles Sketches vs number of items. Once the sketch, of a given K, reaches its "full compaction shape" its size grows very, very slowly. As you can see here, a KllDoubles sketch of 10^10 items would be about 6KB in size. The KllFloats sketch is about half that. This means for practical stream sizes, the KLL sketches stay pretty small.
+
+<img class="doc-img-half" src="{{site.docs_img_dir}}/kll/KllGrowthPath_Floats&Doubles.png" alt="KllGrowthPath_Floats&Doubles.png" />
+
+The growth path for KLL can be estimated from equations and plots that predict the size of the sketch fairly accurately. The following plot shows the growth path normalized per byte of item size. This can be used even for items of variable size as long as you can estimate the average item size.
+
+<img class="doc-img-half" src="{{site.docs_img_dir}}/kll/NormalizedGrowth_1B_K200.png" alt="NormalizedGrowth_1B_K200.png" />
+
+A KLL sketch of a larger"K", would shift this graph to the right. A smaller "K" would shift it to the left.
diff --git a/docs/img/kll/KllGrowthPath_Floats&Doubles.png b/docs/img/kll/KllGrowthPath_Floats&Doubles.png
new file mode 100644
index 00000000..effdc616
Binary files /dev/null and b/docs/img/kll/KllGrowthPath_Floats&Doubles.png differ
diff --git a/docs/img/kll/NormalizedGrowth_1B_K200.png b/docs/img/kll/NormalizedGrowth_1B_K200.png
new file mode 100644
index 00000000..acd179c9
Binary files /dev/null and b/docs/img/kll/NormalizedGrowth_1B_K200.png differ


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