Update KLL and Quantiles Overview documents. master
authorLee Rhodes <leerho@users.noreply.github.com>
Fri, 30 Sep 2022 18:37:20 +0000 (14:37 -0400)
committerLee Rhodes <leerho@users.noreply.github.com>
Fri, 30 Sep 2022 18:37:20 +0000 (14:37 -0400)
_includes/downloadsInclude.txt
_includes/toc.html
docs/Community/Research.md
docs/KLL/KLLAccuracyAndSize.md [new file with mode: 0644]
docs/KLL/KLLSketch.md
docs/Quantiles/QuantilesOverview.md
docs/Quantiles/QuantilesReferences.md
docs/Quantiles/QuantilesSketchOverview.md
docs/Quantiles/SketchingQuantilesAndRanksTutorial.md
docs/Tuple/TupleEngagementExample.md
src/main/resources/docgen/toc.json

index 874b3e3af64ce05a5b3f09be548c2172840d768b..f74acb49ec2d61393dd96d2b959e79d6b55d87e9 100644 (file)
@@ -3,8 +3,9 @@
 | Component | Release | ZIP | ASC | SHA512 | Date-Time | SVN ID | Committer |
 |:---------:|:-------:|:---:|:---:|:------:|:---------:|:------:|:---------:|
 | Java Core | 3.3.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/java/3.3.0/apache-datasketches-java-3.3.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/java/3.3.0/apache-datasketches-java-3.3.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/java/3.3.0/apache-datasketches-java-3.3.0-src.zip.sha512) | 2022-06-06T20:43:49Z | 54934 | dcromberge |
+| C++,Python Core | 3.4.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/cpp/3.4.0/apache-datasketches-cpp-3.4.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/cpp/3.4.0/apache-datasketches-cpp-3.4.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/cpp/3.4.0/apache-datasketches-cpp-3.4.0-src.zip.sha512) | 2022-05-21T05:15:07Z | 54660 | jmalkin |
 | C++,Python Core | 3.5.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/cpp/3.5.0/apache-datasketches-cpp-3.5.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/cpp/3.5.0/apache-datasketches-cpp-3.5.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/cpp/3.5.0/apache-datasketches-cpp-3.5.0-src.zip.sha512) | 2022-07-13T21:09:54Z | 55727 | alsay |
-| Java Memory | 2.1.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/memory/2.1.0/apache-datasketches-memory-2.1.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/memory/2.1.0/apache-datasketches-memory-2.1.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/memory/2.1.0/apache-datasketches-memory-2.1.0-src.zip.sha512) | 2022-05-19T14:22:38Z | 54630 | dcromberge |
+| Java Memory | 2.2.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/memory/2.2.0/apache-datasketches-memory-2.2.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/memory/2.2.0/apache-datasketches-memory-2.2.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/memory/2.2.0/apache-datasketches-memory-2.2.0-src.zip.sha512) | 2022-08-15T12:10:22Z | 56289 | dcromberge |
 | Java Hive Adaptor | 1.2.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/hive/1.2.0/apache-datasketches-hive-1.2.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/hive/1.2.0/apache-datasketches-hive-1.2.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/hive/1.2.0/apache-datasketches-hive-1.2.0-src.zip.sha512) | 2022-03-07T23:30:20Z | 52909 | alsay |
 | Java Pig Adaptor | 1.1.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/pig/1.1.0/apache-datasketches-pig-1.1.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/pig/1.1.0/apache-datasketches-pig-1.1.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/pig/1.1.0/apache-datasketches-pig-1.1.0-src.zip.sha512) | 2022-02-17T19:42:16Z | 52612 | alsay |
 | C++ PostgreSQL Adaptor | 1.5.0 | [Download](https://www.apache.org/dyn/closer.lua/datasketches/postgresql/1.5.0/apache-datasketches-postgresql-1.5.0-src.zip) | [Signature](https://downloads.apache.org/datasketches/postgresql/1.5.0/apache-datasketches-postgresql-1.5.0-src.zip.asc) | [Hash](https://downloads.apache.org/datasketches/postgresql/1.5.0/apache-datasketches-postgresql-1.5.0-src.zip.sha512) | 2021-08-09T22:54:59Z | 49403 | alsay |
index 4641b845c9c5dacc002bb46955f6cb94e35d3f1b..c2b650f9710ebecd5bcb783ebf414b2a8be03efc 100644 (file)
       <li><a href="{{site.docs_dir}}/Quantiles/SketchingQuantilesAndRanksTutorial.html">•Quantiles and Ranks Tutorial</a></li>
       <li><a href="{{site.docs_dir}}/Quantiles/QuantilesOverview.html">•Quantiles Overview</a></li>
       <li><a href="{{site.docs_dir}}/KLL/KLLSketch.html">•KLL Floats sketch</a></li>
+      <li><a href="{{site.docs_dir}}/KLL/KLLAccuracyAndSize.html">•KLL Sketch Accuracy and Size</a></li>
       <li><a href="{{site.docs_dir}}/REQ/ReqSketch.html">•REQ Floats sketch</a></li>
       <li><a href="{{site.docs_dir}}/Quantiles/OrigQuantilesSketch.html">•Original QuantilesSketch</a></li>
 
index bb66641c7652d43e4f9a4bf5f4c3b29c4cd83877..a7ad6a5163fb2403d06aeb602e4d24ac8c90fa84 100644 (file)
@@ -147,3 +147,4 @@ This solution suffices in some applications, but for other applications the chun
 
 **[VSGB05]** Shobha Venkataraman, Dawn Xiaodong Song, Phillip B. Gibbons, and Avrim Blum. New streaming algorithms for fast detection of superspreaders. In *Internet Society NDSS Proceedings*, 2005.
 
+**[CKLTV]** Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý. Relative Error Streaming Quantiles. In *PODS '21 Proceedings*, 2021.
diff --git a/docs/KLL/KLLAccuracyAndSize.md b/docs/KLL/KLLAccuracyAndSize.md
new file mode 100644 (file)
index 0000000..acbebfd
--- /dev/null
@@ -0,0 +1,117 @@
+---
+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.
+-->
+# KLL Sketch Accuracy and Size
+
+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).
+
+The accuracy of quantiles sketches is specified and measured with respect to the *rank* only, not the quantiles.
+
+The KLL Sketch has *absolute error*. For example, a specified rank accuracy of 1% at the median (rank = 0.50) means that the true quantile (if you could extract it from the set) should be between *getQuantile(0.49)* and *getQuantile(0.51)*. 
+This same 1% error applied at a rank of 0.95 means that the true quantile should be between *getQuantile(0.94)* and *getQuantile(0.96)*. In other words, the error is a fixed +/- epsilon for the entire range of ranks.
+
+The approximate rank error values listed in the second row of the header in the table below can be computed using the function <i>KLLSketch.getNormalizedRankError(int k, false)</i>. The third row shows the double-sided error that applies to a portion of the distribution such as an element of PMF (bar in a histogram) that is a subject to rank error on both sides. It can be computed using the function <i>KLLSketch.getNormalizedRankError(int k, true)</i>.
+
+## KllFloatsSketch (Java) or kll_sketch&lt;float&gt; (C++) serialized size in bytes from *K* or rank error % vs. *N*.
+
+| N                  | K=25   | K=50  | K=100 | K=200 | K=400 | K=800  | K=1600 |
+| ------------------ | ------ | ----- | ----- | ----- | ----- | ------ | ------ |
+| single-sided error | 10.04% | 5.12% | 2.61% | 1.33% | 0.68% | 0.35%  | 0.18%  |
+| double-sided error | 11.74% | 6.11% | 3.18% | 1.65% | 0.86% | 0.45%  | 0.23%  |
+| 0                  | 8      | 8     | 8     | 8     | 8     | 8      | 8      |
+| 1                  | 40     | 40    | 40    | 40    | 40    | 40     | 40     |
+| 2                  | 44     | 44    | 44    | 44    | 44    | 44     | 44     |
+| 4                  | 52     | 52    | 52    | 52    | 52    | 52     | 52     |
+| 8                  | 68     | 68    | 68    | 68    | 68    | 68     | 68     |
+| 16                 | 100    | 100   | 100   | 100   | 100   | 100    | 100    |
+| 32                 | 120    | 164   | 164   | 164   | 164   | 164    | 164    |
+| 64                 | 188    | 196   | 292   | 292   | 292   | 292    | 292    |
+| 128                | 220    | 336   | 352   | 548   | 548   | 548    | 548    |
+| 256                | 268    | 396   | 632   | 664   | 1,060 | 1,060  | 1,060  |
+| 512                | 288    | 524   | 744   | 1,224 | 1,288 | 2,084  | 2,084  |
+| 1,024              | 356    | 568   | 988   | 1,436 | 2,404 | 2,536  | 4,132  |
+| 2,048              | 392    | 556   | 1,036 | 1,912 | 2,812 | 4,768  | 5,032  |
+| 4,096              | 428    | 628   | 1,012 | 1,996 | 3,740 | 5,580  | 9,492  |
+| 8,192              | 448    | 656   | 1,004 | 2,156 | 3,844 | 7,440  | 11,116 |
+| 16,384             | 496    | 708   | 1,224 | 2,148 | 4,104 | 7,648  | 14,820 |
+| 32,768             | 528    | 740   | 1,260 | 2,344 | 4,384 | 8,236  | 15,228 |
+| 65,536             | 556    | 764   | 1,292 | 2,120 | 4,664 | 8,772  | 16,236 |
+| 131,072            | 612    | 800   | 1,304 | 2,436 | 4,740 | 9,280  | 17,592 |
+| 262,144            | 632    | 844   | 1,352 | 2,464 | 4,744 | 8,644  | 18,268 |
+| 524,288            | 680    | 880   | 1,392 | 2,512 | 4,780 | 9,344  | 18,724 |
+| 1,048,576          | 720    | 916   | 1,436 | 2,548 | 4,772 | 9,560  | 18,932 |
+| 2,097,152          | 744    | 948   | 1,460 | 2,584 | 4,860 | 9,584  | 19,008 |
+| 4,194,304          | 780    | 1,000 | 1,500 | 2,616 | 4,928 | 9,572  | 18,892 |
+| 8,388,608          | 812    | 1,032 | 1,540 | 2,640 | 4,960 | 9,656  | 19,036 |
+| 16,777,216         | 852    | 1,052 | 1,584 | 2,680 | 5,000 | 9,708  | 19,204 |
+| 33,554,432         | 892    | 1,108 | 1,620 | 2,724 | 5,032 | 9,728  | 18,620 |
+| 67,108,864         | 928    | 1,124 | 1,648 | 2,760 | 5,040 | 9,764  | 19,276 |
+| 134,217,728        | 936    | 1,168 | 1,688 | 2,780 | 5,100 | 9,808  | 19,304 |
+| 268,435,456        | 964    | 1,200 | 1,696 | 2,832 | 5,136 | 9,848  | 19,336 |
+| 536,870,912        | 992    | 1,232 | 1,752 | 2,868 | 5,176 | 9,876  | 19,396 |
+| 1,073,741,824      | 1,020  | 1,284 | 1,784 | 2,888 | 5,212 | 9,924  | 19,404 |
+| 2,147,483,648      | 1,080  | 1,308 | 1,824 | 2,924 | 5,244 | 9,956  | 19,448 |
+| 4,294,967,296      | 1,108  | 1,356 | 1,864 | 2,976 | 5,264 | 9,980  | 19,488 |
+| 8,589,934,592      | 1,148  | 1,384 | 1,888 | 2,992 | 5,312 | 10,032 | 19,540 |
+| 17,179,869,184     | 1,188  | 1,432 | 1,936 | 3,040 | 5,344 | 10,052 | 19,576 |
+
+## KllDoublesSketch (Java) or kll_sketch&lt;double&gt; (C++) serialized size in bytes from *K* or rank error % vs. *N*.
+
+| N                  | K=25   | K=50  | K=100 | K=200 | K=400  | K=800  | k=1600 |
+| ------------------ | ------ | ----- | ----- | ----- | ------ | ------ | ------ |
+| single-sided error | 10.04% | 5.12% | 2.61% | 1.33% | 0.68%  | 0.35%  | 0.18%  |
+| double-sided error | 11.74% | 6.11% | 3.18% | 1.65% | 0.86%  | 0.45%  | 0.23%  |
+| 0                  | 8      | 8     | 8     | 8     | 8      | 8      | 8      |
+| 1                  | 56     | 56    | 56    | 56    | 56     | 56     | 56     |
+| 2                  | 64     | 64    | 64    | 64    | 64     | 64     | 64     |
+| 4                  | 80     | 80    | 80    | 80    | 80     | 80     | 80     |
+| 8                  | 112    | 112   | 112   | 112   | 112    | 112    | 112    |
+| 16                 | 176    | 176   | 176   | 176   | 176    | 176    | 176    |
+| 32                 | 212    | 304   | 304   | 304   | 304    | 304    | 304    |
+| 64                 | 348    | 364   | 560   | 560   | 560    | 560    | 560    |
+| 128                | 408    | 644   | 676   | 1,072 | 1,072  | 1,072  | 1,072  |
+| 256                | 500    | 760   | 1,236 | 1,300 | 2,096  | 2,096  | 2,096  |
+| 512                | 536    | 1,012 | 1,456 | 2,420 | 2,548  | 4,144  | 4,144  |
+| 1,024              | 668    | 1,096 | 1,940 | 2,840 | 4,780  | 5,044  | 8,240  |
+| 2,048              | 736    | 1,068 | 2,032 | 3,788 | 5,592  | 9,508  | 10,036 |
+| 4,096              | 804    | 1,208 | 1,980 | 3,952 | 7,444  | 11,128 | 18,956 |
+| 8,192              | 840    | 1,260 | 1,960 | 4,268 | 7,648  | 14,844 | 22,200 |
+| 16,384             | 932    | 1,360 | 2,396 | 4,248 | 8,164  | 15,256 | 29,604 |
+| 32,768             | 992    | 1,420 | 2,464 | 4,636 | 8,720  | 16,428 | 30,416 |
+| 65,536             | 1,044  | 1,464 | 2,524 | 4,184 | 9,276  | 17,496 | 32,428 |
+| 131,072            | 1,152  | 1,532 | 2,544 | 4,812 | 9,424  | 18,508 | 35,136 |
+| 262,144            | 1,188  | 1,616 | 2,636 | 4,864 | 9,428  | 17,232 | 36,484 |
+| 524,288            | 1,280  | 1,684 | 2,712 | 4,956 | 9,496  | 18,628 | 37,392 |
+| 1,048,576          | 1,356  | 1,752 | 2,796 | 5,024 | 9,476  | 19,056 | 37,804 |
+| 2,097,152          | 1,400  | 1,812 | 2,840 | 5,092 | 9,648  | 19,100 | 37,952 |
+| 4,194,304          | 1,468  | 1,912 | 2,916 | 5,152 | 9,780  | 19,072 | 37,716 |
+| 8,388,608          | 1,528  | 1,972 | 2,992 | 5,196 | 9,840  | 19,236 | 38,000 |
+| 16,777,216         | 1,604  | 2,008 | 3,076 | 5,272 | 9,916  | 19,336 | 38,332 |
+| 33,554,432         | 1,680  | 2,116 | 3,144 | 5,356 | 9,976  | 19,372 | 37,160 |
+| 67,108,864         | 1,748  | 2,144 | 3,196 | 5,424 | 9,988  | 19,440 | 38,468 |
+| 134,217,728        | 1,764  | 2,228 | 3,272 | 5,460 | 10,104 | 19,524 | 38,520 |
+| 268,435,456        | 1,816  | 2,288 | 3,284 | 5,560 | 10,172 | 19,600 | 38,580 |
+| 536,870,912        | 1,868  | 2,348 | 3,392 | 5,628 | 10,248 | 19,652 | 38,696 |
+| 1,073,741,824      | 1,920  | 2,448 | 3,452 | 5,664 | 10,316 | 19,744 | 38,708 |
+| 2,147,483,648      | 2,036  | 2,492 | 3,528 | 5,732 | 10,376 | 19,804 | 38,792 |
+| 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 |
index 6fc9614b5f12ddb8a38d94e727342bfbf03c936e..cded5c545d451d65c2f80a5d1d5ced3a7f653a99 100644 (file)
@@ -25,9 +25,12 @@ Implementation of a very compact quantiles sketch with lazy compaction scheme an
 See <a href="https://arxiv.org/abs/1603.05346v2">Optimal Quantile Approximation in Streams, by Zohar Karnin, Kevin Lang, Edo Liberty</a>.
 The name KLL is composed of the initial letters of the last names of the authors.
 
-The usage of KllSketch is very similar to DoublesSketch. The key feature of this sketch is its compactness for a given accuracy.  It is implemented with both float and double values and can be configured for use on-heap or off-heap (Direct mode).
-The parameter K that affects the accuracy and the size of the sketch is not restricted to powers of 2.
-The default of 200 was chosen to yield approximately the same normalized rank error (1.65%) as the original DoublesSketch (K=128, error 1.73%). 
+The usage of KllSketch is very similar to the classic quantiles DoublesSketch. 
+
+* The key feature of this sketch is its compactness for a given accuracy.  
+* It is separately implemented for both float and double values and can be configured for use on-heap or off-heap (Direct mode).
+* The parameter K that affects the accuracy and the size of the sketch is not restricted to powers of 2.
+* The default of 200 was chosen to yield approximately the same normalized rank error (1.65%) as the classic quantiles DoublesSketch (K=128, error 1.73%). 
 
 ### Java example
 
@@ -45,17 +48,17 @@ double rankOf1000 = sketch.getRank(1000);
 
 ### Differences of KllSketch from the original quantiles DoublesSketch
 
-* KLL has a smaller size for the same accuracy
-* KLL is slightly faster to update
-* The KLL parameter K doesn't have to be power of 2
-* KLL operates with either float values or double values
-* KLL uses a merge method rather than a union object
+* KLL has a smaller size for the same accuracy.
+* KLL is slightly faster to update.
+* The KLL parameter K doesn't have to be power of 2.
+* KLL operates with either float values or double values.
+* KLL uses a merge method rather than a union object.
 
 The starting point for the comparison is setting K in such a way that rank error would be approximately the same. As pointed out above, the default K for both sketches should achieve this. Here is the comparison of the single-sided normalized rank error (getRank() method) for the default K:
 
 <img class="doc-img-full" src="{{site.docs_img_dir}}/kll/kll200-vs-ds128-rank-error.png" alt="RankError" />
 
-DoublesSketch has two forms with different serialized sizes: UpdateDoublesSketch and CompactDoublesSketch. The KLL sketches makes this distinction differently. When the KllSketch is serialized using *toByteArray()* it is always in a compact form and immutable. When the KllSketch is on-heap it is always updatable. It can be created off-heap using the static factory method *newDirectInstance(...)* method, which is also updatable. It is possible to move from off-heap (Direct) to on-heap using the *heapify(Memory)* method.  The *merge(...)* method will work with off-heap sketches, on-heap sketches and Memory wrapped compact byte arrays. 
+The classic quantiles DoublesSketch has two forms with different serialized sizes: UpdateDoublesSketch and CompactDoublesSketch. The KLL sketches makes this distinction differently. When the KllSketch is serialized using *toByteArray()* it is always in a compact form and immutable. When the KllSketch is on-heap it is always updatable. It can be created off-heap using the static factory method *newDirectInstance(...)* method, which is also updatable. It is possible to move from off-heap (Direct) to on-heap using the *heapify(Memory)* method.  The *merge(...)* method will work with off-heap sketches, on-heap sketches and Memory wrapped compact byte arrays. 
 
 Here is the comparison of serialized sizes:
 
index 9cb1dd8b95e77274b37dbd4e0d95a83b9e0de0f9..9cd46dd5d08c44a5731beebb1d6b700d4b56d06a 100644 (file)
@@ -24,7 +24,13 @@ layout: doc_page
 ## Quantile-type sketches in the library
 
 
-There are three types of quantiles sketches in the library. These sketches have many parallel methods. Please refer to the individual Javadocs for more information. 
+This is an overview of the three types of quantiles sketches in the library. Each of these quantile types may have one or more specific implementtaions. 
+
+The mathematical error bounds of all the quantile sketches is specified with respect to rank and not with respect to quantiles.  In other words, the difference between the rank upper bound and the rank lower bound is the confidence interval and can be expressed as a percent of the overall rank distribution (which is 1.0) and is the mathematically derived error for a specific configuration of the sketch.  
+
+Although the quantile upper bound and quantile lower bounds can be approximately computed from the rank upper bound and rank lower bound, and the difference between the quantile bounds is also an approximate confidence interval, the size of the quantile confidence interval may not be meaningful and is not constrained by the defined error of the sketch.
+
+These sketches have many parallel methods. Please refer to the individual Javadocs for more information. 
 
 ### The REQ Sketch
 
@@ -36,12 +42,12 @@ There are three types of quantiles sketches in the library. These sketches have
        * Release 2.2.0, Soon
        * Repo: <https://github.com/apache/datasketches-cpp>
        * Directory: req
-* Key Features
+* Key Features (both Java & C++)
        * Accuracy %: a function of *K* and **relative** with respect to rank. The user can select either High Rank Accuracy (HRA) or Low Rank Accuracy (LRA). This enables extremely high accuracy for the ends of the rank domain. E.g., 99.999%ile quantiles.
-       * User selectable comparison criteria: 
-               * Less-Than (LT), which is compatible with the KLL and older Quantiles Sketch
-               * Less-Than-or-Equals (LE), a common definition in some of the theoretical literature.
-       * Java: Dedicated *float* implementation
+       * User selectable comparison QuantileSearchCriteria: 
+               * Exclusive, which is compatible with the KLL and older Quantiles Sketch
+               * Inclusive, a common definition in some of the theoretical literature.
+       * Java: Dedicated *float* implementation.
        * C++: Template implementation for arbitrary comparible types.
        * Python: Dedicated *float* and *integer* implementations.
 
@@ -55,10 +61,13 @@ There are three types of quantiles sketches in the library. These sketches have
        * Release 1.0.0, 17 Sep 2019
        * Repo: <https://github.com/apache/datasketches-cpp>
        * Directory: kll
-* Key Features
-       * Accuracy %: a function of *K* and independent of rank.* 
+* Key Features (both Java & C++)
+       * User selectable comparison QuantileSearchCriteria: 
+               * Exclusive, which is compatible with the KLL and older Quantiles Sketch
+               * Inclusive, a common definition in some of the theoretical literature.
+       * Accuracy %: a function of *K* and independent of rank. 
        * Near optimal accuracy per sketch size compared to other constant accuracy quantiles sketches. 
-       * Java: Dedicated *float* implementation
+       * Java: Dedicated *float* and *double* implementations.
        * C++: Template implementation for arbitrary comparible types.
        * Python: Dedicated *float* and *integer* implementations
 
@@ -69,9 +78,16 @@ There are three types of quantiles sketches in the library. These sketches have
        * Release 0.3.0, 25 Jan 2016
        * Repo: <https://github.com/apache/datasketches-java>
        * Package: org.apache.datasketches.quantiles
-* Key Features
+* C++, Python
+       * Release 1.0.0, 17 Sep 2019
+       * Repo: <https://github.com/apache/datasketches-cpp>
+       * Directory: 
+* Key Features (both Java & C++)
+    * User selectable comparison QuantileSearchCriteria: 
+               * Exclusive, which is compatible with the KLL and older Quantiles Sketch
+               * Inclusive, a common definition in some of the theoretical literature. 
        * Accuracy %: a function of *K* and independent of rank. 
-       * Dedicated *double* implentation
+       * Dedicated *double* implentation.
        * java generic implementation for arbitrary comparible types.
        * The dedicated *double* implementation can be configured for off-heap operation.
        
index 52b8000aaf5a7eca20d6afc266541bff528f26ed..b9fcc9a51184691d269590e35637d18e0fd7c12a 100644 (file)
@@ -30,3 +30,4 @@ layout: doc_page
 * In J. Gehrke M. Garofalakis and R. Rastogi, editors, In Data Stream Management: Processing High-Speed Data Streams. Springer, 2016.
 * David Felber and Rafail Ostrovsky. A randomized online quantile summary in O((1/ε) log(1/ε))
 * Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý. Relative Error Streaming Quantiles. https://arxiv.org/abs/2004.01668.
+* Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý. Relative Error Streaming Quantiles. In *PODS '21 Proceedings*, 2021.
index 7d195e7758bc7b6f6d0ab84b54526b1d322083c1..a06299b2f001b2a87c49a9aed18cf9ab73b43c29 100644 (file)
@@ -25,8 +25,8 @@ Package: org.apache.datasketches.quantiles
 
 This is a stochastic streaming sketch that enables near-real time analysis of the 
 approximate distribution of comparable values from a very large stream in a single pass. 
-The analysis is obtained using a getQuantiles() function or its inverse functions the 
-Probability Mass Function from getPMF() and the Cumulative Distribution Function from getCDF().
+The analysis is obtained using a getQuantiles() function or its inverse functions, the 
+Probability Mass Function, getPMF(), and the Cumulative Distribution Function, getCDF().
 
 * **NOTE:** See also the <a href="{{site.docs_dir}}/KLL/KLLSketch.html">KLL Sketch</a>.
 
@@ -89,8 +89,7 @@ way off.
 
 ### More Code Snippets
 
-Code examples are best gleaned from the test code that exercises all the various capabilities of the
-sketch.  Here are some brief snippets, simpler than the above graphs, to get you started.
+Code examples are best gleaned from the test code that exercises all the various capabilities of the sketch.  Here are some brief snippets, simpler than the above graphs, to get you started.
 
 #### Median and Top Quartile
 
@@ -247,8 +246,7 @@ Using a simple binary search you can now split your data into the 10 partitions.
 The quantiles algorithm is an implementation of the Low Discrepancy Mergeable Quantiles Sketch, using double values, described in section 3.2 of the journal version of the paper "Mergeable Summaries" by Agarwal, Cormode, Huang, Phillips, Wei, and Yi. 
 <a href="http://dblp.org/rec/html/journals/tods/AgarwalCHPWY13"></a> <!-- does not work with https -->
 
-This algorithm is independent of the distribution of values, which can be anywhere in the
-range of the IEEE-754 64-bit doubles. 
+This algorithm is independent of the distribution of values, which can be anywhere in the range of the IEEE-754 64-bit doubles. 
 
 This algorithm intentionally inserts randomness into the sampling process for values that
 ultimately get retained in the sketch. The result is that this algorithm is not 
index e92478f77ce93d423ad292cd99f11c87be054937..3627d8c94a7c06fb359ac8cbd96bfeb51cd77bbe 100644 (file)
@@ -19,7 +19,7 @@ layout: doc_page
     specific language governing permissions and limitations
     under the License.
 -->
-# Sketching Quantiles and Ranks, the Basics
+# Sketching Quantiles and Ranks Tutorial
 Streaming quantiles algorithms, or quantiles sketches, enable us to analyze the distributions 
 of massive data very quickly using only a small amount of space.  
 They allow us to compute quantile values given a desired rank, or compute a rank given
@@ -34,7 +34,7 @@ of quantiles, ranks and their functions.
 
 The actual enumeration can be done in several ways, but for our use here we will define the two common ways that *rank* can be specified and that we will use. 
 
-* The **natural rank** is a **natural number** from the set of one-based, natural numbers, &#8469;<sub>1</sub>, and is derived by enumerating an ordered set of values, starting with the value 1, up to *n*, the number of values in the set.
+* The **natural rank** is a **natural number** from the set of one-based, natural numbers, &#8469;<sub>1</sub>, and is derived by enumerating an ordered set of values, starting with the value 1, up to *n*, the number of values in the original set.
 
 * The ***normalized rank*** is a number between 0.0 and 1.0 computed by dividing the *natural rank* by the total number of values in the set, *n*. Thus, for finite sets, any *normalized rank* is in the range (0, 1]. Normalized ranks are often written as a percent. But don't confuse percent with percentile! This will be explained below.
 * A rank of 0, whether natural or normalized, represents the empty set.
@@ -65,9 +65,12 @@ Let's examine the following table:
 | Natural Rank    | 1   | 2   | 3   | 4   | 5   |
 | Normalized Rank | .2  | .4  | .6  | .8  | 1.0 |
 
+### Note: 
+The term "value" can be ambiguous because items that we stream into a sketch are values and numeric ranks are also values.  To avoid this ambiguity, we will use the term "quantiles" to refer to values that are streamed into a sketch even before they have been associated with a rank.  
+
 Let's define the simple functions
 
-### ***quantile(rank)*** or ***q(r)*** := return the quantile value ***q*** associated with a given ***rank, r***.
+### ***quantile(rank)*** or ***q(r)*** := return the quantile ***q*** associated with a given ***rank, r***.
 
 ### ***rank(quantile)*** or ***r(q)*** := return the rank ***r*** associated with a given ***quantile, q***.  
 
@@ -90,18 +93,17 @@ Because of the close, two-way relationship of quantiles and ranks,
 And this is certainly true of the table above.
 
 ## The challenge of duplicates
-With real data we often encounter duplicate values in the stream. Let's examine this next table.
+With real data we often encounter duplicate quantiles in the stream. Let's examine this next table.
 
 | Quantile:    | 10  | 20  | 20  | 20  | 50  |
 | ------------ | --- | --- | --- | --- | --- |
 | Natural Rank | 1   | 2   | 3   | 4   | 5   |
 
-As you can see *q(r)* is straightforward. But how about *r(q)*?  Which of the rank values 2, 3, or 4 should the function return given the value 20?  Given this data, and our definitions so far, 
-the function *r(q)* is ambiguous. We will see how to resolve this shortly.
+As you can see *q(r)* is straightforward. But how about *r(q)*?  Which of the ranks 2, 3, or 4 should the function return, given the quantile 20?  Given this data, and our definitions so far, the function *r(q)* is ambiguous. We will see how to resolve this shortly.
  
 
 ## The challenge of approximation
-By definition, sketching algorithms are approximate, and they achieve their high performance by discarding  data.  Suppose you feed *n* items into a sketch that retains only *m < n* items. This means *n-m* values were discarded.  The sketch must track the value *n* used for computing the rank and quantile functions. When the sketch reconstructs the relationship between ranks and values *n-m* rank values are missing creating holes in the sequence of ranks. For example, examine the following tables.
+By definition, sketching algorithms are approximate, and they achieve their high performance by discarding data.  Suppose you feed *n* quantiles into a sketch that retains only *m < n* quantiles. This means *n-m* quantiles were discarded.  The sketch must track the quantity *n* used for computing the rank and quantile functions. When the sketch reconstructs the relationship between ranks and quantiles, *n-m* quantiles are missing creating holes in the ordered sequence. For example, examine the following tables.
 
 The raw data might look like this, with its associated natural ranks.
 
@@ -109,18 +111,18 @@ The raw data might look like this, with its associated natural ranks.
 | ------------ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
 | Natural Rank | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  |
 
-The sketch might discard the even values producing something like this:
+The sketch might discard the even numbered quantiles producing something like this:
 
 | Quantile:    | 10  | 30  | 50  | 70  | 90  |
 | ------------ | --- | --- | --- | --- | --- |
 | Natural Rank | 2   | 4   | 6   | 8   | 10  |
 
-When the sketch deletes values it adjusts the associated ranks by effectively increasing the "weight" of adjacent items so that they are positionally approximately correct and the top rank corresponds to *n*.
+When the sketch deletes quantiles it adjusts the associated ranks by effectively increasing the "weight" of adjacent quantiles so that they are approximately positionally correct and the top natural rank corresponds to *n*.
 
 How do we resolve *q(3)* or *r(20)*?
 
 ## The need for inequality search
-The quantile sketch algorithms discussed in the literature primarily differ by how they choose which values in the stream should be discarded. After the elimination process, all of the quantiles sketch implementations are left with the challenge of how to reconstruct the actual distribution, approximately and with good accuracy. 
+The quantile sketch algorithms discussed in the literature primarily differ by how they choose which quantiles in the stream should be discarded. After the elimination process, all of the quantiles sketch implementations are left with the challenge of how to reconstruct the actual distribution, approximately and with good accuracy. 
 
 Given the presence of duplicates and absence of values from the stream we must redefine the above quantile and rank functions as inequalities **while retaining the properties of 1:1 functions.**
 
@@ -128,77 +130,183 @@ One can find examples of the following definitions in the research literature.
 
 These next examples use a small data set that mimics what could be the result of both duplication and sketch data deletion.
 
+## The rules for returned quantiles or ranks
+
+* **Rule 1:** Every quantile that exists in the input stream or retained by the sketch has an associated rank.
+
+* **Rule 2:** All of our quantile sketches only retain quantiles that exist in the actual input stream of quantiles. 
+
+* **Rule 3:** For the *getQuantile(rank)* queries, all of our quantile sketches only return quantiles that were retained by the sketch. (i.e, we do not interpolate between quantiles.)
+
+* **Rule 4:** For the *getRank(quantile)* queries, all of our quantile sketches only return ranks that are associated with quantiles retained by the sketch. (i.e, we do not interpolate between ranks.)
+
+* **Rule 5:** All of our quantile algorithms compensate for quantiles removed during the sketch quantile selection and compression process by increasing the weights of some of the quantiles not selected for removal, such that:
+
+     * The sum of the natural weights of all quantiles retained by the sketch equals **n**, the total count of all quantiles given to the sketch.
+     * And by corollary, the largest quantile, when sorted by cumulative rank, has a cumulative natural rank of **n**, or equivalently, a cumulative normalized rank of **1.0**.
+
+
 ## The rank functions with inequalities
 
-### ***rank(quantile, NON_INCLUSIVE)*** or ***r(q, LT)*** :=<br>Given *q*, return the rank, *r*, of the largest quantile that is strictly *Less Than* *q*.  
+### ***rank(quantile, INCLUSIVE)*** or ***r(q, LE)*** :=<br>Given *q*, return the rank, *r*, of the largest quantile that is less than or equal to *q*.
+
+<b>Implementation:</b>
+
+* Given *q*, search the quantile array until we find the adjacent pair *{q1, q2}* where *q1 <= q < q2*. 
+* Return the rank, *r*, associated with *q1*, the first of the pair. 
+
+<b>Boundary Exceptions:</b>
+
+* **Boundary Rule 1:** If the given *q* is *>=* the quantile associated with the largest cumulative rank retained by the sketch, the function will return the largest cumulative rank, *1.0*.
+* **Boundary Rule 2:** If the given *q* is *<* the quantile associated with the smallest cumulative rank retained by the sketch, the function will return a rank of *0.0*.
+
+<b>Examples using normalized ranks:</b>
+
+* *r(30) = .786* Normal rule applies: *30 <= 30 < 40*, return *r(q1) = .786*.
+
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |
+| Quantile input     |      |      |      |      |      | 30   |      |       |
+| Qualifying pair    |      |      |      |      |      | q1   | q2   |       |
+| Rank result        |      |      |      |      |      | .786 |      |       |
+
+
+* *r(55) = 1.0* Use Boundary Rule 1: *50 <= 55*, return *1.0*.
+
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |   ?   |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |       |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |       |
+| Quantile input     |      |      |      |      |      |      |      |  55   |       |
+| Qualifying pair    |      |      |      |      |      |      |      |  q1   | (q2)  |
+| Rank result        |      |      |      |      |      |      |      | 1.0   |       |
+
+
+* *r(5) = 0.0* Use Boundary Rule 2: *5 < 10*, return *0.0*.
+
+| Quantile[]:        |   ?  | 10   | 20   | 20   | 30   | 30   | 30   | 40    | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    |      | 1    | 3    | 5    | 7    | 9    | 11   | 13    | 14    |
+| Normalized Rank[]: |      | .071 | .214 | .357 | .500 | .643 | .786 | .929  | 1.0   |
+| Quantile input     |   5  |      |      |      |      |      |      |       |       |
+| Qualifying pair    | (q1) |  q2  |      |      |      |      |      |       |       |
+| Rank result        |   0  |      |      |      |      |      |      |       |       |
+
+
+--------
+
+### ***rank(quantile, EXCLUSIVE)*** or ***r(q, LT)*** :=<br>Given *q*, return the rank, *r*, of the largest quantile that is strictly *Less Than* *q*.  
 
 
 <b>Implementation:</b>
-Given *q*, search the quantile array until we find the adjacent pair *{q1, q2}* where *q1 < q <= q2*. Return the rank, *r*, associated with *q1*, the first of the pair.
 
-<b>Boundary Notes:</b>
+* Given *q*, search the quantile array until we find the adjacent pair *{q1, q2}* where *q1 < q <= q2*. 
+* Return the rank, *r*, associated with *q1*, the first of the pair.
+
+<b>Boundary Exceptions:</b>
 
-* If the given *q* is larger than the largest quantile retained by the sketch, the sketch will return the rank of the largest retained quantile.
-* If the given *q* is smaller than the smallest quantile retained by the sketch, the sketch will return a rank of zero.
+* **Boundary Rule 1:** If the given *q* is *>* the quantile associated with the largest cumulative rank retained by the sketch, the sketch will return the the largest cumulative rank, *1.0*.
+* **Boundary Rule 2:** If the given *q* is *<=* the quantile associated with the smallest cumulative rank retained by the sketch, the sketch will return a rank of *0.0*.
 
 <b>Examples using normalized ranks:</b>
 
-* *r(55) = 1.0* 
-* *r(5) = 0.0*
-* *r(30) = .357* (Illustrated in table)
+* *r(30) = .357* Normal rule applies: *20 < 30 <= 30*, return *r(q1) = .357*.
 
 | Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
 | ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
 | Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
 | Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.000 |
-| Quantile input     |      |      |      | 30   | 30   | 30   |      |       |
+| Quantile input     |      |      |      | 30   |      |      |      |       |
 | Qualifying pair    |      |      | q1   | q2   |      |      |      |       |
 | Rank result        |      |      | .357 |      |      |      |      |       |
 
---------
+* *r(55) = 1.0* Use Boundary Rule 1: *50 < 55*, return *1.0*.
 
-### ***rank(quantile, INCLUSIVE)*** or ***r(q, LE)*** :=<br>Given *q*, return the rank, *r*, of the largest quantile that is less than or equal to *q*.
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |   ?   |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |       |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |       |
+| Quantile input     |      |      |      |      |      |      |      |       |  55   |
+| Qualifying pair    |      |      |      |      |      |      |      |  q1   | (q2)  |
+| Rank result        |      |      |      |      |      |      |      | 1.000 |       |
+
+* *r(5) = 0.0* Use Boundary Rule 2: *5 <= 10*, return *0*.
+
+| Quantile[]:        |   ?  | 10   | 20   | 20   | 30   | 30   | 30   | 40    | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    |      | 1    | 3    | 5    | 7    | 9    | 11   | 13    | 14    |
+| Normalized Rank[]: |      | .071 | .214 | .357 | .500 | .643 | .786 | .929  | 1.0   |
+| Quantile input     |   5  |      |      |      |      |      |      |       |       |
+| Qualifying pair    | (q1) |  q2  |      |      |      |      |      |       |       |
+| Rank result        |   0  |      |      |      |      |      |      |       |       |
+
+
+
+## The quantile functions with inequalities
+
+### ***quantile(rank, INCLUSIVE)*** or ***q(r, GE)*** :=<br>Given *r*, return the quantile, *q*, of the smallest rank that is strictly Greater than or Equal to *r*.
 
 <b>Implementation:</b>
-Given *q*, search the quantile array until we find the adjacent pair *{q1, q2}* where *q1 <= q < q2*. Return the rank, *r*, associated with *q1*, the first of the pair. 
 
-<b>Boundary Notes:</b>
+* Given *r*, search the rank array until we find the adjacent pair *{r1, r2}* where *r1 < r <= r2*. 
+* Return the quantile, *q*, associated with *r2*, the second of the pair.
+
+<b>Boundary Exceptions:</b>
 
-* If the given *q* is larger than the largest quantile retained by the sketch, the function will return the rank of the largest retained quantile.
-* If the given *q* is smaller than the smallest quantile retained by the sketch, the function will return a rank of zero.
+* **Boundary Rule 2:** If the given normalized rank, *r*, is *<=* the smallest rank, the function will return the **quantile** associated with the smallest cumulative rank.
 
 <b>Examples using normalized ranks:</b>
 
-* *r(55) = 1.0*
-* *r(5) = 0.0*
-* *r(30) = .786* (Illustrated in table)
+* *q(.786) = 30* Normal rule applies: *.643 < .786 <= .786*, return *q(r2) = 30*.
 
 | Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
 | ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
 | Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
 | Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.000 |
-| Quantile input     |      |      |      | 30   | 30   | 30   |      |       |
-| Qualifying pair    |      |      |      |      |      | q1   | q2   |       |
-| Rank result        |      |      |      |      |      | .786 |      |       |
+| Rank input         |      |      |      |      |      | .786 |      |       |
+| Qualifying pair    |      |      |      |      | r1   | r2   |      |       |
+| Quantile result    |      |      |      |      |      | 30   |      |       |
 
+* *q(1.0) = 50* Normal rule applies: *.929 < 1.0 <= 1.0*, return *q(r2) = 50*.
 
-## The quantile functions with inequalities
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |
+| Rank input         |      |      |      |      |      |      |      | 1.0   |
+| Qualifying pair    |      |      |      |      |      |      |  r1  |  r2   |
+| Quantile result    |      |      |      |      |      |      |      | 50    |
+
+* *q(0.0 <= .071) = 10* Use Boundary Rule 2: *0.0 <= .071*, return *10*.
+
+| Quantile[]:        |   ?  | 10   | 20   | 20   | 30   | 30   | 30   | 40    | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    |      | 1    | 3    | 5    | 7    | 9    | 11   | 13    | 14    |
+| Normalized Rank[]: |      | .071 | .214 | .357 | .500 | .643 | .786 | .929  | 1.0   |
+| Rank input         |  0.0 |      |      |      |      |      |      |       |       |
+| Qualifying pair    | (r1) |  r2  |      |      |      |      |      |       |       |
+| Rank result        |      | 10   |      |      |      |      |      |       |       |
+
+
+--------
 
-### ***quantile(rank, NON_INCLUSIVE)*** or ***q(r, GT)*** :=<br>Given *r*, return the quantile, *q*, of the smallest rank that is strictly Greater Than *r*.
+### ***quantile(rank, EXCLUSIVE)*** or ***q(r, GT)*** :=<br>Given *r*, return the quantile, *q*, of the smallest rank that is strictly Greater Than *r*.
 
 <b>Implementation:</b>
-Given *r*, search the rank array until we find the adjacent pair *{r1, r2}* where *r1 <= r < r2*. Return the quantile associated with *r2*, the second of the pair.
 
-<b>Boundary Notes:</b>
+* Given *r*, search the rank array until we find the adjacent pair *{r1, r2}* where *r1 <= r < r2*. 
+* Return the quantile, *q*, associated with *r2*, the second of the pair.
 
-* If the given normalized rank, *r*, is equal to 1.0, there is no quantile that satisfies this criterion. However, for convenience, the function will return the largest quantile retained by the sketch.
-* If the given normalized rank, *r*, is less than the smallest rank, the function will return the smallest quantile.
+<b>Boundary Exceptions:</b>
+
+* **Boundary Rule 1:** If the given normalized rank, *r*, is equal to 1.0, there is no quantile that satisfies this criterion. However, for convenience, the function will return quantile associated with the largest cumulative rank retained by the sketch.
+* **Boundary Rule 2:** If the given normalized rank, *r*, is less than the smallest rank, the function will return the quantile associated with the smallest cumulative rank retained by the sketch.
 
 <b>Examples using normalized ranks:</b>
 
-* *q(1.0) = 50*
-* *q(0.0) = 10*
-* *q(.357) = 30* (Illustrated in table)
+* *q(.357) = 30* Normal rule applies: *.357 <= .357 < .500*, return *q(r2) = 30*.
 
 | Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
 | ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
@@ -208,49 +316,105 @@ Given *r*, search the rank array until we find the adjacent pair *{r1, r2}* wher
 | Qualifying pair    |      |      | r1   | r2   |      |      |      |       |
 | Quantile result    |      |      |      | 30   |      |      |      |       |
 
---------
+* *q(1.0) = 50* Use Boundary Rule 1 *1.0 <= 1.0 < ?*, return *50*.
 
-### ***quantile(rank, NON_INCLUSIVE_STRICT)*** or ***q(r, GT_STRICT)*** :=<br>Given *r*, return the quantile, *q*, of the smallest rank that is strictly Greater Than *r*.
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |   ?   |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |       |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |       |
+| Rank input         |      |      |      |      |      |      |      | 1.0   |       |
+| Qualifying pair    |      |      |      |      |      |      |      |  r1   | (r2)  |
+| Quantile result    |      |      |      |      |      |      |      |       |  50   |
 
-In <b>STRICT</b> mode, the only difference is the following:
+* *q(0.99) = 50* Normal rule applies *.929 <= .99 < 1.0*, return *50*.
 
-<b>Boundary Notes:</b>
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |
+| Rank input         |      |      |      |      |      |      | .99  |       |
+| Qualifying pair    |      |      |      |      |      |      |  r1  | r2    |
+| Quantile result    |      |      |      |      |      |      |      | 50    |
 
-* If the given normalized rank, *r*, is equal to 1.0, there is no quantile that satisfies this criterion. The function will return *NaN*.
+
+* *q(0.0 <= .071) = 10* Use Boundary Rule 2: *0.0 < .071*, return *10*.
+
+| Quantile[]:        |   ?  | 10   | 20   | 20   | 30   | 30   | 30   | 40    | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    |      | 1    | 3    | 5    | 7    | 9    | 11   | 13    | 14    |
+| Normalized Rank[]: |      | .071 | .214 | .357 | .500 | .643 | .786 | .929  | 1.0   |
+| Rank input         |  0.0 |      |      |      |      |      |      |       |       |
+| Qualifying pair    | (r1) |  r2  |      |      |      |      |      |       |       |
+| Rank result        |      | 10   |      |      |      |      |      |       |       |
 
 
 --------
 
-### ***quantile(rank, INCLUSIVE)*** or ***q(r, GE)*** :=<br>Given *r*, return the quantile, *q*, of the smallest rank that is strictly Greater than or Equal to *r*.
+### ***quantile(rank, EXCLUSIVE_STRICT)*** or ***q(r, GT_STRICT)*** :=<br>Given *r*, return the quantile, *q*, of the smallest rank that is strictly Greater Than *r*.
+
+### Note: This rule is marginal in its usefulness so it is not currently implemented. 
 
 <b>Implementation:</b>
-Given *r*, search the rank array until we find the adjacent pair *{r1, r2}* where *r1 < r <= r2*. Return the quantile, *q*, associated with *r2*, the second of the pair.
 
-<b>Boundary Notes:</b>
+* Given *r*, search the rank array until we find the adjacent pair *{r1, r2}* where *r1 <= r < r2*. 
+* Return the quantile, *q*, associated with *r2*, the second of the pair.
+
+<b>Boundary Exceptions:</b>
 
-* If the given normalized rank, *r*, is equal to 1.0, the function will return the largest quantile retained by the sketch.
-* If the given normalized rank, *r*, is less than the smallest rank, the function will return the smallest quantile.
+* **Boundary Rule 1:** If the given normalized rank, *r*, is equal to *1.0*, there is no quantile that satisfies this criterion. Return *NaN* or *null*.
+* **Boundary Rule 2:** If the given normalized rank, *r*, is less than the smallest rank, the function will return the quantile associated with the smallest cumulative rank retained by the sketch..
 
 <b>Examples using normalized ranks:</b>
 
-For example *q(.786) = 30*
+* *q(.357) = 30* Normal rule applies: *.357 <= .357 < .500*, return *q(r2) = 30*.
 
 | Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
 | ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
 | Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
 | Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.000 |
-| Rank input         |      |      |      |      |      | .786 |      |       |
-| Qualifying pair    |      |      |      |      | r1   | r2   |      |       |
-| Quantile result    |      |      |      |      |      | 30   |      |       |
+| Rank input         |      |      | .357 |      |      |      |      |       |
+| Qualifying pair    |      |      | r1   | r2   |      |      |      |       |
+| Quantile result    |      |      |      | 30   |      |      |      |       |
+
+* *q(1.0) = 50* Use Boundary Rule 1 *1.0 <= 1.0 < ?*, return *NaN or null*.
+
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |   ?   |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |       |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |       |
+| Rank input         |      |      |      |      |      |      |      | 1.0   |       |
+| Qualifying pair    |      |      |      |      |      |      |      |  r1   | (r2)  |
+| Quantile result    |      |      |      |      |      |      |      |       |  NaN or null |
+
+* *q(0.99) = 50* Normal rule applies *.929 <= .99 < 1.0*, return *50*.
+
+| Quantile[]:        | 10   | 20   | 20   | 30   | 30   | 30   | 40   | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
+| Natural Rank[]:    | 1    | 3    | 5    | 7    | 9    | 11   | 13   | 14    |
+| Normalized Rank[]: | .071 | .214 | .357 | .500 | .643 | .786 | .929 | 1.0   |
+| Rank input         |      |      |      |      |      |      | .99  |       |
+| Qualifying pair    |      |      |      |      |      |      |  r1  | r2    |
+| Quantile result    |      |      |      |      |      |      |      | 50    |
+
+* *q(0.0 <= .071) = 10* Use Boundary Rule 2: *0.0 < .071*, return *10*.
+
+| Quantile[]:        |   ?  | 10   | 20   | 20   | 30   | 30   | 30   | 40    | 50    |
+| ------------------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- | ----- |
+| Natural Rank[]:    |      | 1    | 3    | 5    | 7    | 9    | 11   | 13    | 14    |
+| Normalized Rank[]: |      | .071 | .214 | .357 | .500 | .643 | .786 | .929  | 1.0   |
+| Rank input         |  0.0 |      |      |      |      |      |      |       |       |
+| Qualifying pair    | (r1) |  r2  |      |      |      |      |      |       |       |
+| Rank result        |      | 10   |      |      |      |      |      |       |       |
+
 
 
-## These inequality functions maintain the 1:1 functional relationship
+## These inequality functions maintain the 1:1 functional relationship, approximately. 
 
-### The non inclusive search for q(r) is the inverse of the non inclusive search for r(q). 
+### The *exclusive* search for q(r) is the inverse of the *exclusive* search for r(q). 
 
 ##### Therefore, *q = q(r(q))* and *r = r(q(r))*.
 
-### The inclusive search for q(r) is the inverse of the inclusive search for r(q). 
+### The *inclusive* search for q(r) is the inverse of the *inclusive* search for r(q). 
 
 ##### Therefore, *q = q(r(q))* and *r = r(q(r))*.
 
index 9f43d91af385022760f51a728aa3afda7471b3c5..f0508f210928196ee7eb1ce136bd606c858a36cd 100644 (file)
@@ -31,7 +31,7 @@ For example, let's study the following histogram:
 
 The X-axis is the number of days that a specific customer (identified by some unique ID) visits our site in a 30 day period.
 
-The Y-axis is the number of distinct visitors (customers) that have visited our site Y number of times during the 30 day period. 
+The Y-axis is the number of distinct visitors (customers) that have visited our site X number of times during the 30 day period. 
 
 Reading this histogram we can see that about 100 distinct visitors visited our site exactly one day out of the 30 day period. About 11 visitors visited our site on 5 different days of the 30 day period. And, it seems that we have one customer that visited our site every day of the 30 day period!  We certainly want to encourage more of these loyal customers.
 
index 4b2a5a3885d4473be9860222d86f5b7048740660..f2bc3c5ae4b2975712864440bc364584639fe280 100644 (file)
             {"class":"Doc",  "desc" : "Quantiles and Ranks Tutorial",             "dir" : "Quantiles", "file": "SketchingQuantilesAndRanksTutorial"},
             {"class":"Doc",  "desc" : "Quantiles Overview",                       "dir" : "Quantiles", "file": "QuantilesOverview" },
             {"class":"Doc",  "desc" : "KLL Floats sketch",                        "dir" : "KLL", "file": "KLLSketch" },
+            {"class":"Doc",  "desc" : "KLL Sketch Accuracy and Size",             "dir" : "KLL", "file": "KLLAccuracyAndSize" },
             {"class":"Doc",  "desc" : "REQ Floats sketch",                        "dir" : "REQ", "file": "ReqSketch" },
             {"class":"Doc",  "desc" : "Original QuantilesSketch",                 "dir" : "Quantiles", "file": "OrigQuantilesSketch" },