Expand Frequent Items section to include the new FDT sketch.
diff --git a/_includes/toc.html b/_includes/toc.html
index b229e9b..a3a1f97 100644
--- a/_includes/toc.html
+++ b/_includes/toc.html
@@ -21,16 +21,30 @@
<a href="{{site.docs_dir}}/Research.html">Research</a>
</p>
- <p id="frequent-items-sketches">
- <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent">Frequent Items Sketches</a>
+ <p id="frequency-sketches">
+ <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequency">Frequency Sketches</a>
</p>
- <div class="collapse" id="collapse_frequent">
- <li><a href="{{site.docs_dir}}/FrequentItems/FrequentItemsOverview.html">Frequent Items Overview</a></li>
- <li><a href="{{site.docs_dir}}/FrequentItems/FrequentItemsJavaExample.html">Frequent Items Java Example</a></li>
- <li><a href="{{site.docs_dir}}/FrequentItems/FrequentItemsPigUDFs.html">Frequent Items Pig UDFs</a></li>
- <li><a href="{{site.docs_dir}}/FrequentItems/FrequentItemsHiveUDFs.html">Frequent Items Hive UDFs</a></li>
- <li><a href="{{site.docs_dir}}/FrequentItems/FrequentItemsErrorTable.html">Frequent Items Error Table</a></li>
- <li><a href="{{site.docs_dir}}/FrequentItems/FrequentItemsReferences.html">Frequent Items References</a></li>
+ <div class="collapse" id="collapse_frequency">
+ <li><a href="{{site.docs_dir}}/Frequency/FrequencySketchesOverview.html">Frequency Sketches Overview</a></li>
+
+ <p id="frequent-item-sketches">
+ <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent_item">Frequent Item Sketches</a>
+ </p>
+ <div class="collapse" id="collapse_frequent_item">
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentItemsOverview.html">Frequent Items Overview</a></li>
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentItemsJavaExample.html">Frequent Items Java Example</a></li>
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentItemsPigUDFs.html">Frequent Items Pig UDFs</a></li>
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentItemsHiveUDFs.html">Frequent Items Hive UDFs</a></li>
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentItemsErrorTable.html">Frequent Items Error Table</a></li>
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentItemsReferences.html">Frequent Items References</a></li>
+ </div>
+
+ <p id="frequent-distinct-sketches">
+ <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent_distinct">Frequent Distinct Sketches</a>
+ </p>
+ <div class="collapse" id="collapse_frequent_distinct">
+ <li><a href="{{site.docs_dir}}/Frequency/FrequentDistinctTuplesSketch.html">Frequent Distinct Tuples Sketch</a></li>
+ </div>
</div>
<p id="hll-sketches">
@@ -104,6 +118,7 @@
<li><a href="{{site.docs_dir}}/Theta/ConcurrentThetaSketch.html">Concurrent Theta Sketch</a></li>
<li><a href="{{site.docs_dir}}/Theta/ThetaJavaExample.html">Theta Sketch Java Example</a></li>
<li><a href="{{site.docs_dir}}/Theta/ThetaSparkExample.html">Theta Sketch Spark Example</a></li>
+
<p>
<a data-toggle="collapse" class="menu collapsed" href="#collapse_kmv">KMV Tutorial</a>
</p>
diff --git a/docs/Frequency/FrequencySketchesOverview.md b/docs/Frequency/FrequencySketchesOverview.md
new file mode 100644
index 0000000..e1b6ead
--- /dev/null
+++ b/docs/Frequency/FrequencySketchesOverview.md
@@ -0,0 +1,47 @@
+---
+layout: doc_page
+---
+
+## Frequency Sketches Overview
+
+### Frequent Items
+These sketches implement algorithms that are members of a class of "Heavy Hitters" algorithms that identify
+the "heaviest" or "most frequently occurring" items in a stream.
+
+Suppose you have a web-site store that sells songs and you wish to identify the most frequent song-titles
+that are being downloaded from your store.
+
+This is a perfect use-case for the frequencies/ItemsSketch, which is a Generic class that can be configured to
+count the number of occurrences of any arbitrary item. In this case our song-titles are strings. For example,
+
+<pre>
+ ItemsSketch<String> sketch = new ItemsSketch<String>();
+ while (remainingItems) { sketch.update("songTitle"); }
+</pre>
+
+This configures the sketch to track and count frequent occurrences of Strings. And in this case you would update the sketch
+with the title of each song as it appears in the stream. Note that in this case we assume that each occurrence of a song
+title carries with it a "weight" of one. After the sketch has been populated with the stream you query the sketch to get
+a list of the "most frequently occurring" song titles with an approximate count of the actual number of occurences in the stream.
+
+Now suppose your song titles are sold at different prices and you wish to identify the song titles that are generating the most
+revenue. In this case each item can carry a different "weight" which is the price. We can use the same sketch as before, but
+we update it using a "weight".
+
+<pre>
+ ItemsSketch<String> sketch = new ItemsSketch<String>();
+ while (remainingItems) { sketch.update("songTitle", priceCents); }
+</pre>
+
+The sketch only accepts integral values for the weight, so we just multiply the price by 100 to make the weight integer cents
+instead of fractional dollars.
+
+The Frequent Items Sketch is an "aggregating" sketch in that duplicate items in the stream can have different weights and the
+sketch properly tracks the total weight for each distinct item.
+
+### Frequent Distinct Tuples Sketch
+
+This is a very different algorithm that identifies the most frequent distinct occurrences associated with a specific key, and it is
+called the <i>Frequent Distinct Tuples Sketch</i> or <i>FdtSketch</i>. See the documentation for this sketch.
+
+
diff --git a/docs/Frequency/FrequentDistinctTuplesSketch.md b/docs/Frequency/FrequentDistinctTuplesSketch.md
new file mode 100644
index 0000000..4982e26
--- /dev/null
+++ b/docs/Frequency/FrequentDistinctTuplesSketch.md
@@ -0,0 +1,42 @@
+---
+layout: doc_page
+---
+
+## Frequent Distinct Tuples Sketch
+Given a multiset of tuples with dimensions <i>{d1,d2, d3, ..., dN}</i>, and a primary subset of
+dimensions <i>M < N</i>, the task is to identify the combinations of <i>M</i> subset dimensions
+that have the most frequent number of distinct combinations of the <i>N-M</i> non-primary
+dimensions.
+
+We define a specific combination of the <i>M</i> primary dimensions as a <i>Primary Key</i>
+and all combinations of the <i>M</i> primary dimensions as the set of <i>Primary Keys</i>.
+
+We define the set of all combinations of <i>N-M</i> non-primary dimensions associated with a
+single primary key as a <i>Group</i>.
+
+For example, assume <i>N=3, M=2</i>, where the set of Primary Keys are defined by
+<i>{d1, d2}</i>. After populating the sketch with a stream of tuples all of size <i>N</i>,
+we wish to identify the Primary Keys that have the most frequent number of distinct occurrences
+of <i>{d3}</i>. Equivalently, we want to identify the Primary Keys with the largest Groups.
+
+Alternatively, if we choose the Primary Key as <i>{d1}</i>, then we can identify the
+<i>{d1}</i>s that have the largest groups of <i>{d2, d3}</i>. The choice of
+which dimensions to choose for the Primary Keys is performed in a post-processing phase
+after the sketch has been populated. Thus, multiple queries can be performed against the
+populated sketch with different selections of Primary Keys.
+
+As a simple concrete example, let's assume <i>N = 2</i> and let <i>d1 := IP address</i>, and
+<i>d2 := User ID</i>.
+Let's choose <i>{d1}</i> as the Primary Keys, then the sketch allows the identification of the
+<i>IP addresses</i> that have the largest populations of distinct <i>User IDs</i>. Conversely,
+if we choose <i>{d2}</i> as the Primary Keys, the sketch allows the identification of the
+<i>User IDs</i> with the largest populations of distinct <i>IP addresses</i>.
+
+An important caveat is that if the distribution is too flat, there may not be any
+"most frequent" combinations of the primary keys above the threshold. Also, if one primary key
+is too dominant, the sketch may be able to only report on the single most frequent primary
+key combination, which means the possible existance of false negatives.
+
+In this implementation the input tuples presented to the sketch are string arrays.
+
+
diff --git a/docs/FrequentItems/FrequentItemsErrorTable.md b/docs/Frequency/FrequentItemsErrorTable.md
similarity index 100%
rename from docs/FrequentItems/FrequentItemsErrorTable.md
rename to docs/Frequency/FrequentItemsErrorTable.md
diff --git a/docs/FrequentItems/FrequentItemsHiveUDFs.md b/docs/Frequency/FrequentItemsHiveUDFs.md
similarity index 100%
rename from docs/FrequentItems/FrequentItemsHiveUDFs.md
rename to docs/Frequency/FrequentItemsHiveUDFs.md
diff --git a/docs/FrequentItems/FrequentItemsJavaExample.md b/docs/Frequency/FrequentItemsJavaExample.md
similarity index 100%
rename from docs/FrequentItems/FrequentItemsJavaExample.md
rename to docs/Frequency/FrequentItemsJavaExample.md
diff --git a/docs/FrequentItems/FrequentItemsOverview.md b/docs/Frequency/FrequentItemsOverview.md
similarity index 100%
rename from docs/FrequentItems/FrequentItemsOverview.md
rename to docs/Frequency/FrequentItemsOverview.md
diff --git a/docs/FrequentItems/FrequentItemsPigUDFs.md b/docs/Frequency/FrequentItemsPigUDFs.md
similarity index 100%
rename from docs/FrequentItems/FrequentItemsPigUDFs.md
rename to docs/Frequency/FrequentItemsPigUDFs.md
diff --git a/docs/FrequentItems/FrequentItemsReferences.md b/docs/Frequency/FrequentItemsReferences.md
similarity index 100%
rename from docs/FrequentItems/FrequentItemsReferences.md
rename to docs/Frequency/FrequentItemsReferences.md
diff --git a/docs/FrequentItems/data.txt b/docs/Frequency/data.txt
similarity index 100%
rename from docs/FrequentItems/data.txt
rename to docs/Frequency/data.txt
