Sketch Library Dictionary
Refers to sketch accuracy...
The Alpha Theta Choosing Function (TCF) and the theory behind it is fully described in the
Theta Sketch Framework paper.
The alpha algorithm is optimized for speed and accuracy in a real-time sketch
building / estimating environment.
One of the properties of the Alpha Algorithm used for cache management within a sketch is that
the value of Theta Long is always up-to-date. There may be
dirty hash
values in the cache, but the Alpha Algorithm estimation function ignores them.
In Theta Sketches, the default nominal entries of 4096 is provided as a convenience for those cases where the
number of entries is not provided.
A sketch of 4096 entries has a Relative Standard Error (RSE) of +/- 1.56% at a confidence of 68%;
or equivalently, a Relative Error of +/- 3.1% at a confidence of 95.4%.
In Theta Sketches, the default Update Hash Seed 9001 is a prime number that was chosen
very early on in experimental testing.
Choosing a seed is somewhat arbitrary, and this particular seed is not superior to other seeds.
In performing set operations on two sketches it is critical that the same hash
function and seed was used for both sketches, otherwise the assumed 1:1 relationship
between the original source key value and the hashed bit string would be violated.
Once you have developed a history of stored sketches you are stuck with your chosen seed.
So don't change it!
Update Hash Seed
A sketch is considered degenerate if it has never reached reached
Estimation Mode where the count of its retained hash values is
exact and less than Nominal Entries (or k entries)
and no estimation is needed. This is also referred to as Exact Mode.
The destination Memory for this object. If not required it may be null. If not null and large
enough the returned object will be backed by this Memory.
If null, the returned object will be on the Java heap.
In Theta Sketches, this refers to the ordering of hash values in a returned CompactSketch.
If true, the internal hash values will be ordered. This will enable much higher
performance during union (merge) operations but at the cost of a sort, which may not be
desirable in some applications, especially real-time.
For the Theta Alpha Sketch, a retained hash value is considered dirty if it is ≥ Theta Long or < 0.
See Valid Hash.
In Theta Sketches, the state isEmpty() for a sketch means that the sketch cache has zero hash values and that none of the
update methods have been called with valid data. In other words, the sketch has never seen any data.
This state is equivalent to "null" in the sense that it is safe to exclude empty sketches from union operations. However, an empty sketch
will impact intersections and difference set operations.
Note that isEmpty() does not always mean that theta is 1.0 because if p < 1.0, theta will be set
equal to p during construction.
Also, a cache of zero values (getRetainedEntries(true) = 0) does not mean that the sketch is Empty since
set intersection or difference operations can result in a sketch with zero values.
If the sourcing sketches had seen data then a resulting intersection or difference sketch will be not Empty
and have valid upper and lower bounds even if the cache has zero values. In other words, the resulting sketch represents
a valid distribution of data that just happens to have zero samples collected from it.
Note also that a virgin Intersection object will return isEmpty() == false. This is because a virgin Intersection object represents
the Universe Set, which is clearly not empty.
These are subtle distinctions and exist for mathematical correctness. Excluding sketches that just have getRetainedEntries(true) = 0
from set operations them could result in impacting the accuracy of results.
Once a Theta Sketch exceeds the configured Nominal Entries, or k, number of retained hash values,
the sketch transitions into estimation mode where it must now estimate the population of uniques that
the retained entries represent. A sketch can also be in estimation mode if the sketch was configured with a
Sampling Probability < 1.0.
Estimation Mode = (θ < 1.0) & NOT empty.
For Theta Sketches, the Log base 2 of the number of Nominal Entries.
For Theta Sketches, the Log base 2 of the size of the internal hash table in 64-bit longs.
The backing Memory object which may be a source or destination.
For Theta Sketches and depending on the specific sketch, the constructor data type is int or String.
Acceptable values for constructing new sketches are positive integers that are powers of two.
This parameter specifies the target nominal number of entries (a.k.a. k) that will be retained in the internal cache
and ultimately determines the accuracy of the sketch (see Sketch Accuracy).
Internally each entry is retained as a long of 8 bytes.
The reason it is called "nominal" is that depending on the specific algorithm of the sketch, the actual
number of entries retained by the sketch after the sketch goes into estimation mode
may differ from the configured value. For the AlphaSketch the number of retained entries statistically varies
but has a mean of k. For the QuickSelect sketches, the number of retained entries will statistically
vary from k to almost 2*k.
Each sketch type also has a minimum acceptable value for this value. For QuickSelect Sketches this value is 16 and for
Alpha Sketches this value is 512. Specifying a value less than this minimum value just results in the minimum value being used.
This is a positive number, which may be either an integer (1, 2, or 3) or a double ≤ 3.0.
This value is used in the getUpperBounds(int numStdDev) and
getLowerBounds(int numStdDev) methods and represents (theoretically) the +/- standard deviation from the center of the
Standard Normal Gaussian Distribution. For example:
getUpperBound(1) returns the estimated quantile(0.841) of the distribution.
getLowerBound(1) returns the estimated quantile(0.158) of the distribution.
getUpperBound(2) returns the estimated quantile(0.977) of the distribution.
getLowerBound(2) returns the estimated quantile(0.023) of the distribution.
getUpperBound(3) returns the estimated quantile(0.9986) of the distribution.
getLowerBound(3) returns the estimated quantile(0.0013) of the distribution.
However, for sketches with small configured values of Nominal Entries < 4096 for Theta or lgConfigK < 12 for HLL,
the error distribution of the sketch becomes quite asymmetric and cannot be approximated with a Gaussian. In these cases the interpretation of
numStdDev is that of an index that returns the quantile of the sketch error distribution that corresponds to fractional normalized rank
of the standard normal distribution at the specified numStdDev.
Thus, getUpperBound(1) and getLowerBound(2) represent the 68.3% confidence bounds,
getUpperBound(2) and getLowerBound(2) represent the 95.4% confidence bounds, and
getUpperBound(3) and getLowerBound(3) represent the 99.7% confidence bounds.
For some sketches where the error distribution is not Gaussian, special mathematical approximation methods are used.
See Sketch Accuracy.
The fundamental Theta Sketch QuickSelect algorithm is described in classic algorithm texts by Sedgewick and
is the Theta Choosing Function (TCF) for the QuickSelect Sketches.
When the internal hash table of the sketch reaches its internal
refresh threshold,
the quick select algorithm is used to select the (k+1)th order statistic
from the hash table with a complexity of O(n).
The value of the selected hash becomes the new
Theta Long
and immediately makes some number of entries in the table
dirty.
The rebuild() method is called that rebuilds the hash table removing the
dirty values.
Since the value of Theta Long
is only changed when the hash table needs to be rebuilt,
the values in the hash table are only ever dirty
briefly during the rebuild process.
Thus, all the values in the hash table are always
valid during normal updating of the sketch.
One of the benefits of using the QuickSelect algorithm for the cache management of the sketch is
that the number of valid hashes ranges from
nominal entries
to the current REBUILD_THRESHOLD, which is nominally 15/16 * cacheSize.
This means that without the user forcing
a rebuild(), the sketch, on average, may be about 50% larger than
nominal entries, about 19% more accurate, and faster.
For Theta Sketches, the Resize Factor is a dynamic, speed performance vs. memory size tradeoff.
The sketches created on-heap and configured with a Resize Factor of > X1 start out with
an internal hash table size that is the smallest submultiple of the the target
Nominal Entries
and larger than the minimum required hash table size for that sketch.
When the sketch needs to be resized larger, then the Resize Factor is used as a multiplier of
the current sketch cache array size.
"X1" means no resizing is allowed and the sketch will be intialized at full size.
"X2" means the internal cache will start very small and double in size until the target size is reached.
Similarly, "X4" is a factor of 4 and "X8 is a factor of 8.
For Theta Sketches, the uniform random pre-sketching sampling probability.
Depending on the specific sketch, the constructor data type is float or String.
Incoming hashed data values are sampled by this probability factor before being submitted to
the sketching algorithm. For example, if p were set to 0.25, then on average, only one
forth of the incoming values, selected uniformly and at random, would be evaluated by the
sketching algorithm to be retained by the sketch.
Its default value is 1.0 (no sampling).
Its value must be in the range: 0 < p ≤ 1.0.
This mode is particularly useful when merging large numbers of
degenerate sketches.
For Theta Sketches, the long (64-bit) seed is required by the Update Hash Function.
This seed value is intentionally not serialized along with this sketch in order to provide
some security and protection against "dictionary attacks".
In order to provide some protection against accidental mixing
of sketches that were generated with different seeds a short, 16-bit,
Seed Hash is stored with the sketch image.
When heapifying or wrapping an UpdateSketch image, which can be either a byte array or a Memory object,
the user must provide the original seed either directly or indirectly by assuming the DEFAULT_UPDATE_SEED.
The provided seed will be hashed and validated against the internal short Seed Hash and an error will be thrown if the seed hashes do not match.
The Set Operations classes, Union, Intersection and AnotB also require the user to provide the seed either directly or indirectly.
An internal check will be made to make sure that the provided seed does not hash to a 16-bit value of zero.
If it does produce zero, an error will be thrown and the user must provide a different seed value.
See also Default Update Seed.
For Theta and Tuple Sketches, a 16-bit hash of the Update Hash Seed used internally to validate
(1) that two sketches undergoing set operations were, in fact, created using matching Update Hash Seeds;
or (2) that when deserializing or wrapping a sketch image that the caller has the correct seed.
When coordinated hash tables are merged and if the merging process does not update the target sketch with sufficient randomness, clustering
in the target hash table can be greatly exaggerated causing poor speed performance for both updates and searches. This is called the
"snowplow" effect because of the analogy of visualizing the clusters in a hash table as piles of snow that grow larger and larger. Since the
size of the clusters are only represented by their width (not height like piles of snow), the clusters push themselves out horizontally and
merge together as if they were pushed together with a snowplow.
For Theta Sketches, the Theta Choosing Function (TCF) and the theory behind it is fully described in the
Theta Sketch Framework paper.
For Theta Sketches, refers to the mathematical random variable θ that represents the current probability
that the next, non-duplicate unique input value presented to the sketch will change the state of the sketch.
Given N uniquified inputs to a sketch configured to retain at most k hashes of the inputs,
θ ≈ k/N, 0 < θ ≤ 1.0, and θ = (double) thetaLong / Long.MAX_VALUE;.
See thetaLong.
For Theta Sketches, the 64-bit, positive long equivalent of theta where
0 < thetaLong ≤ Long.MAX_VALUE, and thetaLong = θ * Long.MAX_VALUE.
This framework enables sketches with different algorithms and Theta Choosing Functions
to be arguments to the Union, Intersection and AnotB Set Operations.
This framework also enables the sketches to share estimation, upper and lower bounds algorithms and
a common serialization data structure.
The Theta Sketch Framework, Theta Choosing Functions and the theory behind them is fully described
in the Theta Sketch Framework paper.
For Theta Sketches, this provides useful detail for sketch characterization and debugging. It is not required that any of
these values be monitored during normal operation.
The UpdateReturnState is defined as follows:
- InsertedCountIncremented: Inserted, not full, retained_entries_count incremented.
- InsertedCountNotIncremented: Inserted, not full, retained-entries-count not incremented
because a dirty value was overridden.
- RejectedDuplicate: Rejected as duplicate.
- RejectedNullOrEmpty: Rejected because input was null or empty. Only for update objects.
- RejectedOverTheta: Rejected because the computed hash was over the current value of thetaLong.
For Theta Sketches, a retained hash value is considered valid if it is greater than zero and less than
thetaLong. See Dirty Hash.