This is an automated email from the ASF dual-hosted git repository.
git-site-role pushed a commit to branch asf-site
in repository https://gitbox.apache.org/repos/asf/datasketches-website.git
The following commit(s) were added to refs/heads/asf-site by this push:
new 540bf354 Automatic Site Publish by Buildbot
540bf354 is described below
commit 540bf3549117cf58c1816dd9ae0d84c1373223a0
Author: buildbot <[email protected]>
AuthorDate: Fri Sep 20 23:39:17 2024 +0000
Automatic Site Publish by Buildbot
---
output/docs/Theta/ThetaSketchFramework.html | 523 ----------------------------
1 file changed, 523 deletions(-)
diff --git a/output/docs/Theta/ThetaSketchFramework.html
b/output/docs/Theta/ThetaSketchFramework.html
deleted file mode 100644
index 545433ff..00000000
--- a/output/docs/Theta/ThetaSketchFramework.html
+++ /dev/null
@@ -1,523 +0,0 @@
-<!DOCTYPE html>
-<!-- Start _layouts/doc_page.html-->
-<html lang="en">
-
-<head>
-<!-- Start _include/site_head.html -->
-<meta charset="UTF-8">
-<meta name="viewport" content="width=device-width, initial-scale=1.0">
-<meta name="description" content="">
-<meta name="author" content="datasketches">
-
-<title>DataSketches | </title>
-
-<link rel="shortcut icon" href="/img/favicon.png">
-
-<!-- original source:
https://maxcdn.bootstrapcdn.com/font-awesome/4.1.0/css/font-awesome.min.css -->
-<link rel="stylesheet" href="/css/font-awesome.min.css">
-<!-- original source:
https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css -->
-<link rel="stylesheet" href="/css/bootstrap.min.css">
-
-<link rel="stylesheet" href="/css/fonts.css" type="text/css">
-
-<link rel="stylesheet" href="/css/main.css">
-<link rel="stylesheet" href="/css/header.css">
-<link rel="stylesheet" href="/css/footer.css">
-<link rel="stylesheet" href="/css/syntax.css">
-<link rel="stylesheet" href="/css/docs.css">
-
-<script type="text/x-mathjax-config">
- MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'],
['\\(','\\)']]},showMathMenu:false,showMathMenuMSIE:false,showProcessingMessages:false});
-</script>
-
-<!-- original source:
https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMX_HTML-full
-->
-<script src="/js/MathJax.js?config=TeX-AMS_HTML"></script>
-
-<!-- original source: https://code.jquery.com/jquery.min.js -->
-<script src="/js/jquery.min.js"></script>
-
-<!-- original source:
https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js -->
-<script src="/js/bootstrap.min.js"></script> <!-- 3.2.0-->
-<!-- End _include/site_head.html -->
-
-</head>
-
-<body>
-<!-- Start _include/nav_bar.html -->
-<div class="navbar navbar-inverse navbar-static-top ds-nav">
- <div class="container">
- <div class="navbar-header">
- <button type="button" class="navbar-toggle" data-toggle="collapse"
data-target=".navbar-collapse">
- <span class="sr-only">Toggle navigation</span>
- <span class="icon-bar"></span>
- <span class="icon-bar"></span>
- <span class="icon-bar"></span>
- </button>
- <a href="/" style="padding-top: 0px; padding-bottom: 0px;">
- <span class="ds-small-h-logo"></span></a>
- </div>
- <div class="navbar-collapse collapse">
- <ul class="nav navbar-nav navbar-right">
- <li>
- <a href="/docs/Background/TheChallenge.html">
- <span class="fa fa-info-circle"></span> DOCUMENTATION</a>
- </li>
- <li>
- <a href="/docs/Community/Downloads.html">
- <span class="fa fa-download"></span> DOWNLOAD</a>
- </li>
- <!--
- <li>
- <a href="/docs/Architecture/Components.html">
- <span class="fa fa-github"></span> GITHUB</a>
- </li>
- -->
- <li>
- <a href="/docs/Community/Research.html">
- <span class="fa fa-paper-plane"></span> RESEARCH</a>
- </li>
- <li>
- <a href="/docs/Community/index.html" style="padding-top: 0;
padding-bottom: 0;">
- <img class="ds-small-man" src="/img/datasketches-ManWhite.svg"
alt="Man in community">COMMUNITY</a>
- </li>
- <li>
- <ul class="nav navbar-nav navbar-right ds-nav">
- <li class="dropdown ds-nav" >
- <a href="#" class="dropdown-toggle" data-toggle="dropdown"
role="button" aria-haspopup="true" aria-expanded="false" style="padding-top: 0;
padding-bottom: 0;"><img class="apache-logo" src="/img/feather.svg" alt="Apache
feather">Apache <span class="caret"></span></a>
- <ul class="dropdown-menu ds-nav">
- <li><a href="https://www.apache.org/";
target="_blank">Foundation</a></li>
- <li><a href="https://www.apache.org/events/current-event";
target="_blank">Events</a></li>
- <li><a href="https://www.apache.org/licenses/";
target="_blank">License</a></li>
- <li><a
href="https://privacy.apache.org/policies/privacy-policy-public.html";
target="_blank">Privacy Policy</a></li>
- <li><a href="https://www.apache.org/foundation/thanks.html";
target="_blank">Thanks</a></li>
- <li><a href="https://www.apache.org/security/";
target="_blank">Security</a></li>
- <li><a
href="https://www.apache.org/foundation/sponsorship.html";
target="_blank">Sponsorship</a></li>
- </ul>
- </li>
- </ul>
- </li>
- </ul>
- </div>
- </div>
-</div>
-<!-- End _include/nav_bar.html -->
-
-
-<!-- Start _include/javadocs.html -->
-<div class="ds-header">
- <div class="container">
- <h4>API Latest Releases:
- <a href="https://apache.github.io/datasketches-java/6.1.0/";>Java
Core</a>,
- <a href="https://apache.github.io/datasketches-cpp/5.1.0/";>C++ Core</a>,
- <a href="https://apache.github.io/datasketches-python/5.0.2/";>Python</a>,
- <a href="https://apache.github.io/datasketches-memory/3.0.1/";>Memory</a>,
- <a href="/api/pig/snapshot/apidocs/index.html">Pig</a>,
- <a href="/api/hive/snapshot/apidocs/index.html">Hive</a>,
- </h4>
- </div>
-</div>
-<!-- End _include/javadocs.html -->
-
-
- <div class="container">
- <div class="row">
- <!-- Start ToC Block -->
- <div class="col-md-3">
- <div class="searchbox" style="position:relative">
- <gcse:searchbox-only></gcse:searchbox-only>
- </div>
-<!-- Start _includes/toc.html -->
-<!-- Computer Generated File, Do Not Edit! -->
-<link rel="stylesheet" href="/css/toc.css">
-<div id="toc" class="nav toc hidden-print">
-
- <p id="background">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_background">Background</a>
- </p>
- <div class="collapse" id="collapse_background">
- <li><a href="/docs/Background/TheChallenge.html">•The Challenge</a></li>
- <li><a href="/docs/Background/SketchOrigins.html">•Sketch Origins</a></li>
- <li><a href="/docs/Background/SketchElements.html">•Sketch
Elements</a></li>
- <li><a href="/docs/Background/Presentations.html">•Presentations</a></li>
- <li><a
href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/DataSketches_deck.pdf";>•Overview
Slide Deck</a></li>
- </div>
-
- <p id="architecture-and-design">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_architecture_and_design">Architecture And Design</a>
- </p>
- <div class="collapse" id="collapse_architecture_and_design">
- <li><a href="/docs/Architecture/MajorSketchFamilies.html">•The Major
Sketch Families</a></li>
- <li><a href="/docs/Architecture/LargeScale.html">•Large Scale
Computing</a></li>
- <li><a href="/docs/Architecture/KeyFeatures.html">•Key Features</a></li>
- <li><a href="/docs/Architecture/SketchFeaturesMatrix.html">•Sketch
Features Matrix</a></li>
- <li><a href="/docs/Architecture/Components.html">•Components</a></li>
- <li><a href="/docs/Architecture/SketchesByComponent.html">•Sketches by
Component</a></li>
- <li><a href="/docs/Architecture/SketchCriteria.html">•Sketch
Criteria</a></li>
-
- <p id="memory-component">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_memory_component">Memory Component</a>
- </p>
- <div class="collapse" id="collapse_memory_component">
- <li><a href="/docs/Memory/MemoryComponent.html">•Memory
Component</a></li>
- <li><a href="/docs/Memory/MemoryPerformance.html">•Memory Component
Performance</a></li>
- </div>
- <li><a href="/docs/Architecture/OrderSensitivity.html">•Notes on Order
Sensitivity</a></li>
- <li><a href="/docs/Architecture/Concurrency.html">•Notes on
Concurrency</a></li>
- </div>
-
- <p id="sketch-families">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_sketch_families">Sketch Families</a>
- </p>
- <div class="collapse" id="collapse_sketch_families">
-
- <p id="distinct-counting">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_distinct_counting">Distinct Counting</a>
- </p>
- <div class="collapse" id="collapse_distinct_counting">
- <li><a href="/docs/DistinctCountFeaturesMatrix.html">•Features
Matrix</a></li>
- <li><a href="/docs/DistinctCountMeritComparisons.html">•Figures-of-Merit
Comparison</a></li>
-
- <p id="cpc-sketches">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_cpc_sketches">CPC Sketches</a>
- </p>
- <div class="collapse" id="collapse_cpc_sketches">
- <li><a href="/docs/CPC/CPC.html">•CPC Sketch</a></li>
- <li><a href="/docs/CPC/CpcPerformance.html">•CPC Sketch
Performance</a></li>
-
- <p id="cpc-examples">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_cpc_examples">CPC Examples</a>
- </p>
- <div class="collapse" id="collapse_cpc_examples">
- <li><a href="/docs/CPC/CpcJavaExample.html">•CPC Sketch Java
Example</a></li>
- <li><a href="/docs/CPC/CpcCppExample.html">•CPC Sketch C++
Example</a></li>
- <li><a href="/docs/CPC/CpcPigExample.html">•CPC Sketch Pig
UDFs</a></li>
- <li><a href="/docs/CPC/CpcHiveExample.html">•CPC Sketch Hive
UDFs</a></li>
- </div>
- </div>
-
- <p id="hyperloglog-sketches">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_hyperloglog_sketches">HyperLogLog Sketches</a>
- </p>
- <div class="collapse" id="collapse_hyperloglog_sketches">
- <li><a href="/docs/HLL/HLL.html">•HLL Sketch</a></li>
- <li><a href="/docs/HLL/HllMaxSizeAndErrorTable.html">•HLL Max Size &
Error Table</a></li>
- <li><a href="/docs/HLL/HllMap.html">•HLL Map Sketch</a></li>
-
- <p id="hll-examples">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_hll_examples">HLL Examples</a>
- </p>
- <div class="collapse" id="collapse_hll_examples">
- <li><a href="/docs/HLL/HllJavaExample.html">•HLL Sketch Java
Example</a></li>
- <li><a href="/docs/HLL/HllCppExample.html">•HLL Sketch C++
Example</a></li>
- <li><a href="/docs/HLL/HllPigUDFs.html">•HLL Sketch Pig UDFs</a></li>
- <li><a href="/docs/HLL/HllHiveUDFs.html">•HLL Sketch Hive
UDFs</a></li>
- </div>
-
- <p id="hll-studies">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_hll_studies">HLL Studies</a>
- </p>
- <div class="collapse" id="collapse_hll_studies">
- <li><a href="/docs/HLL/HllPerformance.html">•HLL Sketch
Performance</a></li>
- <li><a href="/docs/HLL/Hll_vs_CS_Hllpp.html">•HLL vs Clearspring
HLL++</a></li>
- <li><a
href="/docs/HLL/HllSketchVsDruidHyperLogLogCollector.html">•HLL Sketch vs Druid
HyperLogLogCollector</a></li>
- </div>
- </div>
- <li><a href="/docs/Theta/ThetaSketches.html">•Theta Sketches</a></li>
- <li><a href="/docs/Tuple/TupleSketches.html">•Tuple Sketches</a></li>
- </div>
-
- <p id="most-frequent">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_most_frequent">Most Frequent</a>
- </p>
- <div class="collapse" id="collapse_most_frequent">
- <li><a href="/docs/Frequency/FrequencySketchesOverview.html">•Frequency
Sketches Overview</a></li>
-
- <p id="frequent-item-sketches">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_frequent_item_sketches">Frequent Item Sketches</a>
- </p>
- <div class="collapse" id="collapse_frequent_item_sketches">
- <li><a href="/docs/Frequency/FrequentItemsOverview.html">•Frequent
Items Overview</a></li>
- <li><a href="/docs/Frequency/FrequentItemsErrorTable.html">•Frequent
Items Error Table</a></li>
- <li><a href="/docs/Frequency/FrequentItemsReferences.html">•Frequent
Items References</a></li>
- <li><a href="/docs/Frequency/FrequentItemsPerformance.html">•Frequent
Items Performance</a></li>
-
- <p id="most-frequent-examples">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_most_frequent_examples">Most Frequent Examples</a>
- </p>
- <div class="collapse" id="collapse_most_frequent_examples">
- <li><a
href="/docs/Frequency/FrequentItemsJavaExample.html">•Frequent Items Java
Example</a></li>
- <li><a href="/docs/Frequency/FrequentItemsCppExample.html">•Frequent
Items C++ Example</a></li>
- <li><a href="/docs/Frequency/FrequentItemsPigUDFs.html">•Frequent
Items Pig UDFs</a></li>
- <li><a href="/docs/Frequency/FrequentItemsHiveUDFs.html">•Frequent
Items Hive UDFs</a></li>
- </div>
- </div>
-
- <p id="frequent-distinct-sketches">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_frequent_distinct_sketches">Frequent Distinct Sketches</a>
- </p>
- <div class="collapse" id="collapse_frequent_distinct_sketches">
- <li><a
href="/docs/Frequency/FrequentDistinctTuplesSketch.html">•Frequent Distinct
Tuples Sketch</a></li>
- </div>
- </div>
-
- <p id="quantiles-and-histograms">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_quantiles_and_histograms">Quantiles And Histograms</a>
- </p>
- <div class="collapse" id="collapse_quantiles_and_histograms">
- <li><a
href="/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">•Quantiles and
Ranks Tutorial</a></li>
- <li><a href="/docs/Quantiles/QuantilesOverview.html">•Quantiles
Overview</a></li>
- <li><a href="/docs/KLL/KLLSketch.html">•KLL Sketch Family</a></li>
- <li><a href="/docs/KLL/KLLAccuracyAndSize.html">•KLL Sketch Accuracy and
Size</a></li>
- <li><a href="/docs/KLL/UnderstandingKLLBounds.html">•Understanding KLL
Bounds</a></li>
- <li><a href="/docs/REQ/ReqSketch.html">•REQ Floats sketch</a></li>
- <li><a href="/docs/Quantiles/ClassicQuantilesSketch.html">•Classic
Quantiles Sketches</a></li>
-
- <p id="quantiles-examples">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_quantiles_examples">Quantiles Examples</a>
- </p>
- <div class="collapse" id="collapse_quantiles_examples">
- <li><a href="/docs/Quantiles/QuantilesJavaExample.html">•Quantiles
Sketch Java Example</a></li>
- <li><a href="/docs/KLL/KLLCppExample.html">•KLL Quantiles Sketch C++
Example</a></li>
- <li><a href="/docs/Quantiles/QuantilesPigUDFs.html">•Quantiles Sketch
Pig UDFs</a></li>
- <li><a href="/docs/Quantiles/QuantilesHiveUDFs.html">•Quantiles Sketch
Hive UDFs</a></li>
- </div>
-
- <p id="quantiles-studies">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_quantiles_studies">Quantiles Studies</a>
- </p>
- <div class="collapse" id="collapse_quantiles_studies">
- <li><a
href="/docs/QuantilesStudies/DruidApproxHistogramStudy.html">•Druid Approximate
Histogram</a></li>
- <li><a href="/docs/QuantilesStudies/MomentsSketchStudy.html">•Moments
Sketch Study</a></li>
- <li><a
href="/docs/QuantilesStudies/QuantilesStreamAStudy.html">•Quantiles StreamA
Study</a></li>
- <li><a href="/docs/QuantilesStudies/ExactQuantiles.html">•Exact
Quantiles for Studies</a></li>
- </div>
-
- <p id="quantiles-sketch-theory">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_quantiles_sketch_theory">Quantiles Sketch Theory</a>
- </p>
- <div class="collapse" id="collapse_quantiles_sketch_theory">
- <li><a
href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/Quantiles_KLL.pdf";>•Optimal
Quantile Approximation in Streams</a></li>
- <li><a href="/docs/Quantiles/QuantilesReferences.html">•Quantiles
References</a></li>
- </div>
- </div>
-
- <p id="sampling">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_sampling">Sampling</a>
- </p>
- <div class="collapse" id="collapse_sampling">
- <li><a href="/docs/Sampling/ReservoirSampling.html">•Reservoir
Sampling</a></li>
- <li><a
href="/docs/Sampling/ReservoirSamplingPerformance.html">•Reservoir Sampling
Performance</a></li>
- <li><a href="/docs/Sampling/VarOptSampling.html">•VarOpt
Sampling</a></li>
-
- <p id="sampling-examples">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_sampling_examples">Sampling Examples</a>
- </p>
- <div class="collapse" id="collapse_sampling_examples">
- <li><a href="/docs/Sampling/ReservoirSamplingJava.html">•Reservoir
Sampling Java Example</a></li>
- <li><a href="/docs/Sampling/ReservoirSamplingPigUDFs.html">•Reservoir
Sampling Pig UDFs</a></li>
- <li><a href="/docs/Sampling/VarOptSamplingJava.html">•VarOpt Sampling
Java Example</a></li>
- <li><a href="/docs/Sampling/VarOptPigUDFs.html">•VarOpt Sampling Pig
UDFs</a></li>
- </div>
- </div>
- </div>
-
- <p id="system-integrations">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_system_integrations">System Integrations</a>
- </p>
- <div class="collapse" id="collapse_system_integrations">
- <li><a href="/docs/SystemIntegrations/ApacheDruidIntegration.html">•Using
Sketches in ApacheDruid</a></li>
- <li><a href="/docs/SystemIntegrations/ApacheHiveIntegration.html">•Using
Sketches in Apache Hive</a></li>
- <li><a href="/docs/SystemIntegrations/ApachePigIntegration.html">•Using
Sketches in Apache Pig</a></li>
- <li><a href="/docs/SystemIntegrations/ApachePinotIntegration.html">•Using
Sketches in Apache Pinot</a></li>
- <li><a href="/docs/SystemIntegrations/PostgreSQLIntegration.html">•Using
Sketches in PostgreSQL</a></li>
- </div>
-
- <p id="community">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_community">Community</a>
- </p>
- <div class="collapse" id="collapse_community">
- <li><a href="/docs/Community/index.html">•Community</a></li>
- <li><a href="/docs/Community/Downloads.html">•Downloads</a></li>
- <li><a href="/docs/Community/NewCommitterProcess.html">•Committer
Process</a></li>
- <li><a href="/docs/Community/ReleaseProcessForCppComponents.html">•Release
Process For CPP Components</a></li>
- <li><a
href="/docs/Community/ReleaseProcessForJavaComponents.html">•Release Process
For Java Components</a></li>
- <li><a href="/docs/Community/Transitioning.html">•Transitioning from prior
GitHub Site</a></li>
- </div>
-
- <p id="research">
- <a data-toggle="collapse" class="menu collapsed"
href="#collapse_research">Research</a>
- </p>
- <div class="collapse" id="collapse_research">
- <li><a href="/docs/Community/Research.html">•Research</a></li>
- </div>
-</div>
-<!-- End _includes/toc.html -->
-
-
-<!-- Start _includes/tocScript.html -->
-<script>
- (function () {
-
- var findLineItem = function (path) {
- return document.querySelector(`#toc [href="${path}"]`);
- };
-
- function findNavItem(path) {
- return document.querySelector(`.nav [href="${path}"]`);
- }
-
- var highlighLineItem = function (element) {
- element.classList.add('highlight');
- };
-
- var checkHasClass = function (element, className) {
- return element.className.split(' ').find(function (item) { return item
=== className || '' })
- }
-
- var findAllCollapseParents = function (element) {
- var collapseMenus = [];
- var elementPointer = element;
- while (elementPointer !== document.body) {
- if (checkHasClass(elementPointer, 'collapse')) {
- collapseMenus.push(elementPointer);
- }
- elementPointer = elementPointer.parentElement
- }
- return collapseMenus
- };
-
- var openMenuItem = function (element) {
- // $(element).collapse('show') would start a transition, adding `in`
class instead.
- element.classList.add('in');
- };
-
- var openAllFromList = function (elementList) {
- elementList.forEach(openMenuItem);
- };
-
- var highlightAndOpenMenu = function () {
- // Highlight & expand nav item in the TOC
- var currentLineItem = findLineItem(document.location.pathname);
- highlighLineItem(currentLineItem);
- openAllFromList(findAllCollapseParents(currentLineItem));
-
- // Highlight nav item in top navigation
- highlighLineItem(findNavItem(document.location.pathname));
- };
-
- $(highlightAndOpenMenu);
-
- }());
-</script>
-<!-- End _includes/tocScript.html -->
-
- </div>
- <!-- End ToC Block -->
- <div class="col-md-9 doc-content">
-<!--
- 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.
--->
-<h2 id="theta-sketch-framework">Theta Sketch Framework</h2>
-<p>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.</p>
-
-<p>The <a
href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/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="https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchEquations.pdf";>Theta
Sketch Equations</a> document.</p>
-
-<p>The TSF consists of the following components:</p>
-
-<ol>
- <li>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>.</li>
- <li>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.</li>
- <li>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.</li>
-</ol>
-
-<p>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.</p>
-
-<p>Note that in the KMV sketch the value <i>k</i> is overloaded with multiple
roles:</p>
-
-<ol>
- <li><i>k</i> determines the RSE (accuracy) of the sketch</li>
- <li><i>k</i> determines the upper-bound size of the sketch</li>
- <li><i>k</i> is used as a constant in the estimator and RSE equations</li>
- <li><i>k</i> determines the <i>V(k<sup>th</sup>)</i> threshold, used to
reject/accept hash values into the cache.</li>
-</ol>
-
-<p>By unloading some of these roles, we will gain degrees of freedom to do
some innovative things.</p>
-
-<p>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></p>
-
-<p>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.</p>
-
-<p>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.</p>
-
-<p><img class="doc-img-full" src="/docs/img/theta/ThetaSketch1.png"
alt="ThetaSketch1" /></p>
-
-<p>[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.</p>
-
-<p>[2] See <a href="/docs/Theta/KMVempty.html">KMV Tutorial</a> for a brief
tutorial on KMV Sketches.</p>
-
-<p>[3] This is a limited “KMV perspective” on how <i>θ</i> gets assigned. The
attached paper
-<a
href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/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.</p>
-
- </div> <!-- End content -->
- </div> <!-- End row -->
- </div> <!-- End Container -->
-
-<!-- Start _include/page_footer.html -->
-<footer class="ds-footer">
- <div class="container">
- <div class="text-center">
- <p>
- <div>Copyright © 2024 <a href="https://www.apache.org";>Apache Software
Foundation</a>,
- Licensed under the Apache License, Version 2.0. All Rights Reserved.
- | <a
href="https://privacy.apache.org/policies/privacy-policy-public.html";>Privacy
Policy</a><br>
- Apache DataSketches, Apache, the Apache feather logo, and the Apache
DataSketches project logos are trademarks of The Apache Software Foundation.<br>
- All other marks mentioned may be trademarks or registered trademarks
of their respective owners.
- </div>
-
- </div>
- </div>
-</footer>
-<!-- End _include/page_footer.html -->
-
-</body>
-
-</html>
-<!-- End _layouts/doc_page.html-->
\ No newline at end of file
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
