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:29 UTC
(datasketches-website) branch fix_tuple_toc created (now e838ff07)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch fix_tuple_toc
in repository https://gitbox.apache.org/repos/asf/datasketches-website.git
at e838ff07 Refactor of ThetaSketches - Try 1
This branch includes the following new commits:
new e838ff07 Refactor of ThetaSketches - Try 1
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-website) 01/01: Refactor of ThetaSketches - Try 1
Posted by le...@apache.org.
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