Add Moments Sketch and Quantiles Sketch studies
diff --git a/_includes/toc.html b/_includes/toc.html
index 53ec56c..f0129c2 100644
--- a/_includes/toc.html
+++ b/_includes/toc.html
@@ -69,7 +69,9 @@
<div class="collapse" id="collapse_quantilesStudies">
<li><a href="{{site.docs_dir}}/Quantiles/KLLSketch.html">New KLL sketch and comparison with DoublesSketch</a></li>
<li><a href="{{site.docs_dir}}/Quantiles/KllSketchVsTDigest.html">KLL sketch vs t-digest</a></li>
- <li><a href="{{site.docs_dir}}/Quantiles/DruidApproxHistogramStudy.html">Druid Approximate Histogram Study</a></li>
+ <li><a href="{{site.docs_dir}}/Quantiles/DruidApproxHistogramStudy.html">Druid Approximate Histogram</a></li>
+ <li><a href="{{site.docs_dir}}/Quantiles/MomentsSketchStudy.html">Moments Sketch Study</a></li>
+ <li><a href="{{site.docs_dir}}/Quantiles/QuantilesStreamAStudy.html">Quantiles StreamA Study</a></li>
</div>
<p>
diff --git a/docs/Quantiles/DruidApproxHistogramStudy.md b/docs/Quantiles/DruidApproxHistogramStudy.md
index 785f834..c1a8577 100644
--- a/docs/Quantiles/DruidApproxHistogramStudy.md
+++ b/docs/Quantiles/DruidApproxHistogramStudy.md
@@ -25,7 +25,7 @@
Unfortunately, a lot of the data that we tend to analyze is highly skewed so these caveats don't bode well for this study. Nonetheless, we thought it would be useful to test it anyway.
## The Input Data
-The data file used for this evaluation, *streamA.txt*, is real data extracted from one of our back-end servers. It represents one hour of time-spent data. The data in this file has a smooth and well-behaved value distribution and has a wide dynamic range. It is a text file and consists of consecutive strings of numeric values separated by a line-feeds. Its size is about 2GB.
+The data file used for this evaluation, *streamA.txt*, is real data extracted from one of our back-end servers. It represents one hour of web-site time-spent data measured in milliseconds. The data in this file has a smooth and well-behaved value distribution with a wide dynamic range. It is a text file and consists of consecutive strings of numeric values separated by a line-feeds. Its size is about 2GB.
## Creating the Exact CDF and Histograms For Comparison
In order to measure the accuracy of the Approximate Histogram, we need an exact, brute-force analysis of *streamA.txt*.
@@ -37,7 +37,7 @@
<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/DruidAH_StreamA_CDF.png" alt="Druid Approx Hist CDF of ranks to quantiles" />
-The green dots in the above plot represents the Gold Standard cumulative distribution (CDF) of ranks to quantile values. The black circles in the upper right corner of the plot represent the values returned from the Approximate Histogram *getQuantiles(float[])* function.
+The green dots in the above plot represents the Exact cumulative distribution (CDF) of ranks to quantile values. The black circles in the upper right corner of the plot represent the values returned from the Approximate Histogram *getQuantiles(float[])* function.
The plot reveals a dramatic failure of the Approximate Histogram. Below rank = 0.89, the returned array had all zeros.
diff --git a/docs/Quantiles/ExactQuantiles.md b/docs/Quantiles/ExactQuantiles.md
index 337b98d..b562f04 100644
--- a/docs/Quantiles/ExactQuantiles.md
+++ b/docs/Quantiles/ExactQuantiles.md
@@ -31,7 +31,7 @@
We choose, somewhat arbitrarily, to select the percentile ranks in order to understand what kind of distribution we are dealing with.
We scan the array and save the 101 quantile values corresponding to this linear series of ranks: (0, .01, .02, ... .99, 1.00).
-## Plot The CDF
+## Plot The <i>StreamA</i> CDF
This allows us to plot the rank to quantile cumulative distribution or CDF.
This is normally plotted with ranks (0 to 1.0) on the X-axis and the 101 quantile values on the Y-axis.
This is a very important plot as it tells us a great deal about our data:
@@ -41,7 +41,7 @@
* Do the values span multiple orders-of-magnitude.
* Are there any apparent gaps or jumps in the values?
-### The <i>StreamA</i> Exact CDF
+### The Exact CDF
<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/StreamA_ExactCDF.png" alt="StreamA Exact CDF" />
@@ -58,10 +58,12 @@
## 4th Scan
We scan the array and save the *natural ranks* (indices) at the chosen split-point values.
The difference between adjacent *natural ranks* is the mass (the number of items) between the respective splitpoints.
+
+## Plot The <i>StreamA</i> Histogram
We can plot the Histogram with the split-point values on the X-axis and the differences between the respective *natural ranks* on the Y-axis.
If we plotted the differences between the respective *normalized ranks* on the Y-axis we would have the PMF.
-### The <i>StreamA</i> Exact Histogram
+### The Exact Histogram
<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/StreamA_ExactHistogram.png" alt="StreamA Exact Histogram" />
diff --git a/docs/Quantiles/MomentsSketchStudy.md b/docs/Quantiles/MomentsSketchStudy.md
new file mode 100644
index 0000000..501b60b
--- /dev/null
+++ b/docs/Quantiles/MomentsSketchStudy.md
@@ -0,0 +1,63 @@
+---
+layout: doc_page
+---
+
+# Moments Sketch Study
+
+The goal of this article is to compare the accuracy performance of the Moments Sketch to an exact, brute-force computation using actual data extracted from one of our back-end servers.
+
+Please get familiar with the [Definitions]({{site.docs_dir}}/Quantiles/Definitions.html) for quantiles.
+
+## Versions
+
+* Moments Sketch code as of <a href="https://github.com/apache/incubator-druid/pull/6581">apache/incubator-druid Pull Request 6851 Feb 4, 2019</a>
+
+
+## The Paper
+
+The implementation of this Moments Sketch was based on the July 13, 2018
+[paper](https://arxiv.org/abs/1803.01969)
+by Edward Gan, Jialin Ding, Kai Sheng Tai, Vatsal Sharan, Peter Bailis of Stanford InfoLab. However, it should be noted that the authors of the paper specifially mention the following caveats:
+
+* "The moments sketch accuracy is dataset dependent" Page 9, section 6.2.3.
+* "The moments sketch runs into numeric stability issues past <i>k</i> ≥ 15 on some datasets." Page 9, Section 6.2.2
+* "The moments sketch ... is most useful in datasets without strong discretization ... The maximum entropy principle is less accurate when there are clusters of discrete values in a dataset." Page 2, Section 1.
+
+Unfortunately, real data can be quite ugly as it can be highly skewed and with lots of zeros, nulls, and sometimes negative values.
+
+## The Input Data
+The data file used for this evaluation, *streamA.txt*, is real data extracted from one of our back-end servers. It represents one hour of web-site time-spent data measured in milliseconds. The data in this file has a smooth and well-behaved value distribution with a wide dynamic range. It is a text file and consists of consecutive strings of numeric values separated by a line-feeds. Its size is about 2GB.
+
+## Creating the Exact CDF and Histograms For Comparison
+In order to measure the accuracy of the Approximate Histogram, we need an exact, brute-force analysis of *streamA.txt*.
+
+The process for creating these comparison standards can be found [here]({{site.docs_dir}}/Quantiles/ExactQuantiles.html).
+
+
+## The Results
+
+The CDF plot:
+
+<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/MSketch_StreamA_CDF.png" alt="MSketch CDF of ranks to quantiles" />
+
+The green dots in the above plot represents the Exact cumulative distribution (CDF) of ranks to quantile values. The black circles in the upper right corner of the plot represent the values returned from the Approximate Histogram *getQuantiles(float[])* function.
+
+The plot reveals that the MSketch has improperly shifted the entire distribution by about 12% to the left creating a fixed rank error of at about 12% over the entire range. This is likely due to the zeros that naturally occur in this data. This failure is silent as MSketch does not provide any warning that this kind of distortion might be occurring.
+
+The Msketch does not provide the inverse *getRank(v)* functionality. This means creating a Histogram or PMF from the Msketch is not simple to do.
+
+Users would be well-advised to not use this tool for serious analysis.
+
+## The Evaluation Source
+The following are used to create the plots above.
+
+* [Approximate Histogram profiler](https://github.com/DataSketches/characterization/blob/master/src/main/java/com/yahoo/sketches/characterization/quantiles/MSketchStreamAProfile.java)
+* [AH profiler config](https://github.com/DataSketches/characterization/blob/master/src/main/resources/quantiles/MSketchStreamAJob.conf)
+* [StreamA Data file](https://github.com/DataSketches/characterization/blob/master/streamA.txt.zip) This is stored using git-lfs.
+
+Run the above profilers as a java application and supply the config file as the single argument. The program will check if the data file has been unzipped, and if not it will unzip it for you.
+
+
+
+
+
diff --git a/docs/Quantiles/QuantilesStreamAStudy.md b/docs/Quantiles/QuantilesStreamAStudy.md
new file mode 100644
index 0000000..b9ab569
--- /dev/null
+++ b/docs/Quantiles/QuantilesStreamAStudy.md
@@ -0,0 +1,69 @@
+---
+layout: doc_page
+---
+
+# Quantiles StreamA Study
+
+The goal of this article is to compare the accuracy performance of the DataSketches Quantiles Sketch to an exact, brute-force computation using actual data extracted from one of our back-end servers.
+
+Please get familiar with the [Definitions]({{site.docs_dir}}/Quantiles/Definitions.html) for quantiles.
+
+## Versions
+
+* DataSketches sketches-core, Released Version 0.12.0 <a href="https://search.maven.org/classic/#artifactdetails%7Ccom.yahoo.datasketches%7Csketches-core%7C0.12.0%7Cjar">Maven Central Repository</a> Updated Aug 7, 2018.
+
+
+## The Paper
+
+The implementation of this Quantiles Sketch was originally inspired by
+[Mergable Summaries]https://dl.acm.org/citation.cfm?id=2213562), PODS, May, 2012 paper by Agarwal, Cormode, Huang, Phillips, Wei, and Yi.
+
+## The Input Data
+The data file used for this evaluation, *streamA.txt*, is real data extracted from one of our back-end servers. It represents one hour of web-site time-spent data measured in milliseconds. The data in this file has a smooth and well-behaved value distribution with a wide dynamic range. It is a text file and consists of consecutive strings of numeric values separated by a line-feeds. Its size is about 2GB.
+
+## Creating the Exact CDF and Histograms For Comparison
+In order to measure the accuracy of the Approximate Histogram, we need an exact, brute-force analysis of *streamA.txt*.
+
+The process for creating these comparison standards can be found [here]({{site.docs_dir}}/Quantiles/ExactQuantiles.html).
+
+## The Results
+
+### K = 256, Size = 21408 bytes
+
+<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/DSQSketchK256_StreamA_CDF.png" alt="DataSketches Quantiles Sketch StreamA CDF of ranks to quantiles" />
+
+The green dots in the above plot represents the Exact cumulative distribution (CDF) of ranks to quantile values. The red circles represent the values returned from the DS Quantiles Sketch *getQuantiles(double[])* function.
+
+The plot reveals a very tight fit to the exact quantiles over the full range. The thin black and blue lines just to the left and right of the plotted points represent the lower-bound and upper-bound error derived from the sketch's *getLowerBound()* and *getUpperBound()* functions. The normalized rank error specification for this sketch which was created with *k = 256* is +/- 0.717%.
+
+The next plot is the Histogram generated from the values returned by the *getPMF(double[])* function. Each of the returned values is multiplied by *getN()* to produce the respecive mass of each bin.
+The Green bars represent the Exact Distribution, and the Orange bars represent the results obtained from the DS Quantiles sketch.
+
+<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/DSQsketchK256_StreamA_PMF.png" alt="DataSketches Quantiles Histogrm vs Exact" />
+
+The histogram produced by the DS Quantiles sketch very closely matches the Exact Histogram.
+
+### K = 32, Size = 3232 bytes
+
+The CDF plot:
+
+<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/DSQSketchK32_StreamA_CDF.png" alt="DataSketches Quantiles Sketch StreamA CDF of ranks to quantiles" />
+
+The Histogram plot:
+
+<img class="doc-img-full" src="{{site.docs_img_dir}}/quantiles/DSQsketchK32_StreamA_PMF.png" alt="DataSketches Quantiles Histogrm vs Exact" />
+
+## The Evaluation Source
+The following are used to create the plots above.
+
+* [DSQsketch profiler](https://github.com/DataSketches/characterization/blob/master/src/main/java/com/yahoo/sketches/characterization/quantiles/QuantilesStreamAProfile.java)
+* [DSQsketch K256 config](https://github.com/DataSketches/characterization/blob/master/src/main/resources/quantiles/QuantilesK256StreamAJob.conf)
+* [DSQsketch K32 config](https://github.com/DataSketches/characterization/blob/master/src/main/resources/quantiles/QuantilesK32StreamAJob.conf)
+* [StreamA Data file](https://github.com/DataSketches/characterization/blob/master/streamA.txt.zip) This is stored using git-lfs.
+
+Run the above profilers as a java application and supply the config file as the single argument. The program will check if the data file has been unzipped, and if not it will unzip it for you.
+
+
+
+
+
diff --git a/docs/img/quantiles/DSQsketchK256_StreamA_CDF.png b/docs/img/quantiles/DSQsketchK256_StreamA_CDF.png
new file mode 100644
index 0000000..0fe0430
--- /dev/null
+++ b/docs/img/quantiles/DSQsketchK256_StreamA_CDF.png
Binary files differ
diff --git a/docs/img/quantiles/DSQsketchK256_StreamA_PMF.png b/docs/img/quantiles/DSQsketchK256_StreamA_PMF.png
new file mode 100644
index 0000000..e6e501e
--- /dev/null
+++ b/docs/img/quantiles/DSQsketchK256_StreamA_PMF.png
Binary files differ
diff --git a/docs/img/quantiles/DSQsketchK32_StreamA_CDF.png b/docs/img/quantiles/DSQsketchK32_StreamA_CDF.png
new file mode 100644
index 0000000..d38a3d6
--- /dev/null
+++ b/docs/img/quantiles/DSQsketchK32_StreamA_CDF.png
Binary files differ
diff --git a/docs/img/quantiles/DSQsketchK32_StreamA_PMF.png b/docs/img/quantiles/DSQsketchK32_StreamA_PMF.png
new file mode 100644
index 0000000..aa09ba6
--- /dev/null
+++ b/docs/img/quantiles/DSQsketchK32_StreamA_PMF.png
Binary files differ
diff --git a/docs/img/quantiles/DSQsketch_StreamA_CDF.png b/docs/img/quantiles/DSQsketch_StreamA_CDF.png
deleted file mode 100644
index bda1c07..0000000
--- a/docs/img/quantiles/DSQsketch_StreamA_CDF.png
+++ /dev/null
Binary files differ
diff --git a/docs/img/quantiles/DSQsketch_StreamA_PMF.png b/docs/img/quantiles/DSQsketch_StreamA_PMF.png
deleted file mode 100644
index bc6faff..0000000
--- a/docs/img/quantiles/DSQsketch_StreamA_PMF.png
+++ /dev/null
Binary files differ
