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 2024/09/20 21:36:30 UTC
(datasketches-website) 01/01: Refactor of ThetaSketches - Try 1
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch fix_tuple_toc
in repository https://gitbox.apache.org/repos/asf/datasketches-website.git
commit e838ff07408f033452fa2313b878b39653614700
Author: Lee Rhodes <le...@gmail.com>
AuthorDate: Fri Sep 20 14:36:13 2024 -0700
Refactor of ThetaSketches - Try 1
Also corrected Tuple images.
---
_includes/toc.html | 4 ++
docs/Theta/ThetaSketches.md | 121 ++++++++++++++++++++++++++++++++
docs/Tuple/TupleSketches.md | 8 +++
docs/img/tuple/TupleStartsWithTheta.png | Bin 90611 -> 213101 bytes
docs/img/tuple/TupleWithAttributes.png | Bin 108800 -> 379982 bytes
5 files changed, 133 insertions(+)
diff --git a/_includes/toc.html b/_includes/toc.html
index ade92120..5ab7457e 100644
--- a/_includes/toc.html
+++ b/_includes/toc.html
@@ -94,6 +94,8 @@
</div>
</div>
+ <li><a href="{{site.docs_dir}}/Theta/ThetaSketches.html">•Theta Sketches</a></li>
+
<p id="theta-sketches">
<a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_sketches">Theta Sketches</a>
</p>
@@ -170,7 +172,9 @@
<li><a href="{{site.docs_dir}}/Theta/ThetaReferences.html">•Theta References</a></li>
</div>
</div>
+
<li><a href="{{site.docs_dir}}/Tuple/TupleSketches.html">•Tuple Sketches</a></li>
+
</div>
<p id="most-frequent">
diff --git a/docs/Theta/ThetaSketches.md b/docs/Theta/ThetaSketches.md
new file mode 100644
index 00000000..27bfeb8f
--- /dev/null
+++ b/docs/Theta/ThetaSketches.md
@@ -0,0 +1,121 @@
+---
+layout: doc_page
+---
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing,
+ software distributed under the License is distributed on an
+ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ KIND, either express or implied. See the License for the
+ specific language governing permissions and limitations
+ under the License.
+-->
+## Contents
+<!-- TOC -->
+* [Theta Sketch Framework](#theta-sketch-framework)
+* Theta Examples
+ * [Concurrent Theta Sketch](https://datasketches.apache.org/docs/Theta/ConcurrentThetaSketch.html)
+ * [Theta Sketch Java Example](https://datasketches.apache.org/docs/Theta/ThetaJavaExample.html)
+ * [Theta Sketch Spark Example](https://datasketches.apache.org/docs/Theta/ThetaSparkExample.html)
+ * [Theta Sketch Pig UDFs](https://datasketches.apache.org/docs/Theta/ThetaPigUDFs.html)
+ * [Theta Sketch Hive UDFs](https://datasketches.apache.org/docs/Theta/ThetaHiveUDFs.html)
+* KMV Tutorial
+ * [The Inverse Estimate](https://datasketches.apache.org/docs/Theta/InverseEstimate.html)
+ * [Empty Sketch](https://datasketches.apache.org/docs/Theta/KMVempty.html)
+ * [First Estimator](https://datasketches.apache.org/docs/Theta/KMVfirstEst.html)
+ * [Better Estimator](https://datasketches.apache.org/docs/Theta/KMVbetterEst.html)
+ * [Rejection Rules](https://datasketches.apache.org/docs/Theta/KMVrejection.html)
+ * [Update V(kth) Rule](https://datasketches.apache.org/docs/Theta/KMVupdateVkth.html)
+* Set Operations and P-sampling
+ * [Set Operations](https://datasketches.apache.org/docs/Theta/ThetaSketchSetOps.html)
+ * [Model & Test Set Operations](https://datasketches.apache.org/docs/Theta/ThetaSetOpsCornerCases.html)
+ * [p-Sampling](https://datasketches.apache.org/docs/Theta/ThetaPSampling.html)
+* Accuracy
+ * [Basic Accuracy](https://datasketches.apache.org/docs/Theta/ThetaAccuracy.html)
+ * [Accuracy Plots](https://datasketches.apache.org/docs/Theta/ThetaAccuracyPlots.html)
+ * [Relative Error Table](https://datasketches.apache.org/docs/Theta/ThetaErrorTable.html)
+ * [SetOp Accuracy](https://datasketches.apache.org/docs/Theta/ThetaSketchSetOpsAccuracy.html)
+ * [Unions With Different k](https://datasketches.apache.org/docs/Theta/AccuracyOfDifferentKUnions.html)
+* Size
+ * [Theta Sketch Size](https://datasketches.apache.org/docs/Theta/ThetaSize.html)
+* Speed
+ * [Update Speed](https://datasketches.apache.org/docs/Theta/ThetaUpdateSpeed.html)
+ * [Merge Speed](https://datasketches.apache.org/docs/Theta/ThetaMergeSpeed.html)
+* Theta Sketch Theory
+ * [Theta Sketch Framework (PDF)](https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchFramework.pdf)
+ * [Theta Sketch Equations (PDF)](https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchEquations.pdf)
+ * [Data Sketches (PDF)](https://github.com/apache/datasketches-website/tree/master/docs/pdf/DataSketches.pdf)
+ * [Confidence Intervals; Notes](https://datasketches.apache.org/docs/Theta/ThetaConfidenceIntervals.html)
+ * [Merging Algorithm; Notes](https://datasketches.apache.org/docs/Theta/ThetaMergingAlgorithm.html)
+ * [Theta References](https://datasketches.apache.org/docs/Theta/ThetaReferences.html)
+<!-- TOC -->
+
+<a id="theta-sketch-framework"></a>
+## Theta Sketch Framework
+Theta Sketches are a generalization of the well known <i>K<sup>th</sup> Minimum Value</i> (KMV)<sup>1,2</sup>
+sketches in that KMV sketches are a form of Theta Sketch, but not all Theta Sketches are KMV.
+
+The <a href="{{site.docs_pdf_dir}}/ThetaSketchFramework.pdf">Theta Sketch Framework</a> (TSF)
+is a mathematical framework
+defined in a multi-stream setting that enables set expressions over these streams and encompasses many
+different sketching algorithms. A rudimentary introduction to the mathematics of the simpler sketch algorithms is developed in
+the <a href="{{site.docs_pdf_dir}}/ThetaSketchEquations.pdf">Theta Sketch Equations</a> document.
+
+The TSF consists of the following components:
+
+1. A data type <i>(θ,S)</i>, known as a <i>Theta Sketch</i>, where 0 < <i>θ</i> < 1 is a
+threshold, and <i>S</i>, the number of entries, is the set of all unique hashed stream items 0 < <i>x</i> < 1
+that are less than <i>θ</i>.
+2. A universal "combining function" <i>ThetaUnion</i> that takes as input a collection of <i>Theta Sketches</i>
+and returns a single <i>Theta Sketch</i> that is a <i>Union</i> of the input sketches.
+This combining function is extended to set <i>Intersections</i> and <i>Differences</i> as well.
+3. A estimator function that takes as input a <i>Theta Sketch</i> and returns an estimate of the unique
+hashed stream items presented to all the input sketches.
+
+The TSF enables this sketch library to encompass multiple sketching algorithms including the
+KMV sketch with a common API and greatly simplifies implementation of set
+expressions.
+
+Note that in the KMV sketch the value <i>k</i> is overloaded with multiple roles:
+
+1. <i>k</i> determines the RSE (accuracy) of the sketch
+2. <i>k</i> determines the upper-bound size of the sketch
+3. <i>k</i> is used as a constant in the estimator and RSE equations
+4. <i>k</i> determines the <i>V(k<sup>th</sup>)</i> threshold, used to reject/accept hash values into the cache.
+
+By unloading some of these roles, we will gain degrees of freedom to do some innovative things.
+
+Instead of having to track <i>V(k<sup>th</sup>)</i>, which is a member of the list of hash values,
+we are going to create a separate threshold variable and call it <i>theta (θ)</i>.
+This effectively decouples #3 and #4 above from <i>k</i>. When the sketch is empty <i>θ</i> = 1.0.
+After the sketch has filled with <i>k</i> minimum values <i>θ</i> is still 1.0.
+When the next incoming unique value must be inserted into the sketch the <i>(k+1)<sup>th</sup></i>
+minimum value, is assigned to <i>θ</i> and removed from the cache.<sup>3</sup>
+
+Ultimately, it will be the size of <i>S</i>, <i>|S|</i>, that will determine the stored size of a
+sketch, which decouples #2 above from the value <i>k</i>.
+The <i>Nominal Entries</i> or <i>k</i> is a <i>user specified, configuration parameter</i>,
+which is used by the software to determine the target accuracy of the sketch and the maximum size of the sketch.
+
+The unbiased estimate simplifies to \|S\|/<i>θ</i>, which is just the size of <i>S</i> divided by <i>θ</i>.
+We will discuss the RSE in a later section.
+
+<img class="doc-img-full" src="https://datasketches.apache.org/docs/img/theta/ThetaSketch1.png" alt="ThetaSketch1" />
+
+[1] Z. Bar-Yossef, T. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting distinct elements in a data stream. In <i>Randomization and Approximation Techniques in Computer Science</i>, pages 1–10. Springer, 2002.
+
+[2] See <a href="{{site.docs_dir}}/Theta/KMVempty.html">KMV Tutorial</a> for a brief tutorial on KMV Sketches.
+
+[3] This is a limited "KMV perspective" on how <i>θ</i> gets assigned. The attached paper
+<a href="{{site.docs_pdf_dir}}/ThetaSketchFramework.pdf">Theta Sketch Framework</a>
+presents multiple ways that <i>θ</i> can be assigned using the <i>Theta Choosing Function (TCF)</i>.
+Different sketch algorithms have different TCFs.
diff --git a/docs/Tuple/TupleSketches.md b/docs/Tuple/TupleSketches.md
index d41a2920..5968e2f5 100644
--- a/docs/Tuple/TupleSketches.md
+++ b/docs/Tuple/TupleSketches.md
@@ -19,6 +19,13 @@ layout: doc_page
specific language governing permissions and limitations
under the License.
-->
+## Contents
+<!-- TOC -->
+* [Tuple Sketch Overview](#tuple-sketch-overview)
+* [Tuple Sketch Examples](#tuple-sketch-examples)
+<!-- TOC -->
+
+<a id="tuple-sketch-overview"></a>
## Tuple Sketch Overview
Tuple Sketches are extensions of the Theta Sketch, which can be represented internally as an array of hash values (of unique identifiers) and a value, theta, which represents the effective sampling rate determined by the sketch.
@@ -41,6 +48,7 @@ The Tuple Sketches also provide sufficient methods so that user could develop a
<img class="doc-img-half" src="{{site.docs_img_dir}}/tuple/TupleJoins.png" alt="TupleJoins" />
+<a id="tuple-sketch-examples"></a>
## Tuple Sketch Examples
* [Tuple Java Example](https://datasketches.apache.org/docs/Tuple/TupleJavaExample.html)
diff --git a/docs/img/tuple/TupleStartsWithTheta.png b/docs/img/tuple/TupleStartsWithTheta.png
index e3989f45..7904206d 100644
Binary files a/docs/img/tuple/TupleStartsWithTheta.png and b/docs/img/tuple/TupleStartsWithTheta.png differ
diff --git a/docs/img/tuple/TupleWithAttributes.png b/docs/img/tuple/TupleWithAttributes.png
index 392dc4fa..21d04c5d 100644
Binary files a/docs/img/tuple/TupleWithAttributes.png and b/docs/img/tuple/TupleWithAttributes.png differ
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org