src/main/java/org/apache/datasketches/hll/package-info.java - datasketches-java - Git at Google

 /*
  * 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.
  */

 /**
  * <h1>The DataSketches&trade; HLL sketch family package</h1>
  * {@link org.apache.datasketches.hll.HllSketch HllSketch} and {@link org.apache.datasketches.hll.Union Union}
  * are the public facing classes of this high performance implementation of Phillipe Flajolet's
  * HyperLogLog algorithm[1] but with significantly improved error behavior and important features that can be
  * essential for large production systems that must handle massive data.
  *
  * <h2>Key Features of the DataSketches&trade; HLL Sketch and its companion Union</h2>
  *
  * <h3>Advanced Estimation Algorithms for Optimum Accuracy</h3>
  *
  * <h4>Zero error at low cardinalities</h4>
  * The HLL sketch leverages highly compact arrays and hash tables to keep exact counts until the transition to
  * dense mode is required for space reasons. The result is perfect accuracy for very low cardinalities.
  *
  * <p>Accuracy for very small streams can be important because Big Data is often fragmented into millions of smaller
  * streams (or segments) that inevitably are power-law distributed in size. If you are sketching all these fragments,
  * as a general rule, more than 80% of your sketches will be very small, 20% will be much larger, and only a few very
  * large in cardinality.
  *
  * <h4>HIP / Martingale Estimator</h4>
  * When obtaining a cardinality estimate, the sketch automatically determines if it was the result of the capture of
  * a single stream, or if was the result of certain qualifying union operations. If this is the case the sketch will
  * take advantage of Edith Cohen's Historical Inverse Probability (HIP) estimation algorithm[2], which was
  * also independently developed by Daniel Ting as the Martingale estimation algorithm[3].
  * This will result in a 20% improvement in accuracy over the standard Flajolet estimator.
  * If it is not a single stream or if the specific union operation did not qualify,
  * the estimator will default to the Composite Estimator.
  *
  * <h4>Composite Estimator</h4>
  * This advanced estimator is a blend of several algorithms including new algorithms developed by Kevin Lang for his
  * Compressed Probabilistic Counting (CPC) sketch[4]. These algorithms provide near optimal estimation accuracy
  * for cases that don't qualify for  HIP / Martingale estimation.
  *
  * <p>As a result of all of this work on accuracy, one will get a very smooth curve of the underlying accuracy of the
  * sketch once the statistical randomness is removed through multiple trials. This can be observed in the
  * following graph.</p>
  *
  * <p><img src="doc-files/HLL_HIP_K12T20U20.png" width="500" alt="HLL Accuracy">[6]</p>
  *
  * <p>The above graph has 7 curves. At y = 0, is the median line that hugs the x-axis so closely that it can't be seen.
  * The two curves, just above and just below the x-axis, correspond to +/- 1 standard deviation (SD) of error.
  * The distance between either one of this pair and the x-axis is also known as the Relative Standard Error (RSE).
  * This type of graph for illustrating sketch error we call a "pitchfork plot".</p>
  *
  * <p>The next two curves above and below correspond to +/- 2 SD, and
  * the top-most and bottom-most curves correspond to +/- 3 SD.
  * The chart grid lines are set at +/- multiples of Relative Standard Error (RSE) that correspond to +/- 1,2,3 SD.
  * Below the cardinality of about 512 there is no error at all. This is the point where this particular
  * sketch transitions from sparse to dense (or estimation) mode.</p>
  *
  * <h3>Three HLL Types</h3>
  * This HLL implementation offers three different types of HLL sketch, each with different
  * trade-offs with accuracy, space and performance. These types are selected with the
  * {@link org.apache.datasketches.hll.TgtHllType TgtHllType} parameter.
  *
  * <p>In terms of accuracy, all three types, for the same <i>lgConfigK</i>, have the same error
  * distribution as a function of cardinality.</p>
  *
  * <p>The configuration parameter <i>lgConfigK</i> is the log-base-2 of <i>K</i>,
  * where <i>K</i> is the number of buckets or slots for the sketch. <i>lgConfigK</i> impacts both accuracy and
  * the size of the sketch in memory and when stored.</p>
  *
  * <h4>HLL 8</h4>
  * This uses an 8-bit byte per HLL bucket. It is generally the
  * fastest in terms of update time but has the largest storage footprint of about <i>K</i> bytes.
  *
  * <h4>HLL 6</h4>
  * This uses a 6-bit field per HLL bucket. It is the generally the next fastest
  * in terms of update time with a storage footprint of about <i>3/4 * K</i> bytes.
  *
  * <h4>HLL 4</h4>
  * This uses a 4-bit field per HLL bucket and for large counts may require
  * the use of a small internal auxiliary array for storing statistical exceptions, which are rare.
  * For the values of <i>lgConfigK &gt; 13</i> (<i>K</i> = 8192),
  * this additional array adds about 3% to the overall storage. It is generally the slowest in
  * terms of update time, but has the smallest storage footprint of about <i>K/2 * 1.03</i> bytes.
  *
  * <h3>Off-Heap Operation</h3>
  * This HLL sketch also offers the capability of operating off-heap. Given a <i>WritableMemory[5]</i> object
  * created by the user, the sketch will perform all of its updates and internal phase transitions
  * in that object, which can actually reside either on-heap or off-heap based on how it was
  * configured. In large systems that must update and union many millions of sketches, having the
  * sketch operate off-heap avoids the serialization and deserialization costs of moving sketches from heap to
  * off-heap and back, and reduces the need for garbage collection.
  *
  * <h3>Merging sketches with different configured <i>lgConfigK</i></h3>
  * This enables a user to union a HLL sketch that was configured with, say, <i>lgConfigK = 12</i>
  * with another loaded HLL sketch that was configured with, say, <i>lgConfigK = 14</i>.
  *
  * <p>Why is this important?  Suppose you have been building a history of sketches of your customer's
  * data that go back a full year (or 5 or 10!) that were all configured with <i>lgConfigK = 12</i>. Because sketches
  * are so much smaller than the raw data it is possible that the raw data was discarded keeping only the sketches.
  * Even if you have the raw data, it might be very expensive and time consuming to reload and rebuild all your
  * sketches with a larger more accurate size, say, <i>lgConfigK = 14</i>.
  * This capability enables you to merge last year's data with this year's data built with larger sketches and still
  * have meaningful results.</p>
  *
  * <p>In other words, you can change your mind about what size sketch you need for your application at any time and
  * will not lose access to the data contained in your older historical sketches.</p>
  *
  * <p>This capability does come with a caveat: The resulting accuracy of the merged sketch will be the accuracy of the
  * smaller of the two sketches. Without this capability, you would either be stuck with the configuration you first
  * chose forever, or you would have to rebuild all your sketches from scratch, or worse, not be able to recover your
  * historical data.</p>
  *
  * <h3>Multi-language, multi-platform.</h3>
  * The binary structures for our sketch serializations are language and platform independent.
  * This means it is possible to generate an HLL sketch on a C++ Windows platform and it can be used on a
  * Java or Python Unix platform.
  *
  * <p>[1] Philippe Flajolet, et al, <a href="https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf">
 <i>HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.</i></a>
  * DMTCS proc. <b>AH</b>, 2007, 127-146.
  *
  * <p>[2] Edith Cohen, <a href="https://arxiv.org/pdf/1306.3284.pdf">
 <i>All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis.</i></a>
  * PODS'14, June 22-27, Snowbird, UT, USA.
  *
  * <p>[3] Daniel Ting,
  * <a href="https://research.facebook.com/publications/streamed-approximate-counting-of-distinct-elements">
 <i>Streamed Approximate Counting of Distinct Elements, Beating Optimal Batch Methods.</i></a>
  * KDD'14 August 24, 2014 New York, New York USA.
  *
  * <p>[4] Kevin Lang,
  * <a href="https://arxiv.org/abs/1708.06839">
 <i>Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm.</i></a>
  * arXiv 1708.06839, August 22, 2017, Yahoo Research.
  *
  * <p>[5] Memory Component,
  * <a href="https://datasketches.apache.org/docs/Memory/MemoryComponent.html">
 <i>DataSketches Memory Component</i></a>
  *
  * <p>[6] MacBook Pro 2.3 GHz 8-Core Intel Core i9
  *
  * @see org.apache.datasketches.cpc.CpcSketch
  *
  * @author Lee Rhodes
  * @author Kevin Lang
  */
 package org.apache.datasketches.hll;
	/*
	* 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.
	*/

	/**
	* <h1>The DataSketches™ HLL sketch family package</h1>
	* {@link org.apache.datasketches.hll.HllSketch HllSketch} and {@link org.apache.datasketches.hll.Union Union}
	* are the public facing classes of this high performance implementation of Phillipe Flajolet's
	* HyperLogLog algorithm[1] but with significantly improved error behavior and important features that can be
	* essential for large production systems that must handle massive data.
	*
	* <h2>Key Features of the DataSketches™ HLL Sketch and its companion Union</h2>
	*
	* <h3>Advanced Estimation Algorithms for Optimum Accuracy</h3>
	*
	* <h4>Zero error at low cardinalities</h4>
	* The HLL sketch leverages highly compact arrays and hash tables to keep exact counts until the transition to
	* dense mode is required for space reasons. The result is perfect accuracy for very low cardinalities.
	*
	* <p>Accuracy for very small streams can be important because Big Data is often fragmented into millions of smaller
	* streams (or segments) that inevitably are power-law distributed in size. If you are sketching all these fragments,
	* as a general rule, more than 80% of your sketches will be very small, 20% will be much larger, and only a few very
	* large in cardinality.
	*
	* <h4>HIP / Martingale Estimator</h4>
	* When obtaining a cardinality estimate, the sketch automatically determines if it was the result of the capture of
	* a single stream, or if was the result of certain qualifying union operations. If this is the case the sketch will
	* take advantage of Edith Cohen's Historical Inverse Probability (HIP) estimation algorithm[2], which was
	* also independently developed by Daniel Ting as the Martingale estimation algorithm[3].
	* This will result in a 20% improvement in accuracy over the standard Flajolet estimator.
	* If it is not a single stream or if the specific union operation did not qualify,
	* the estimator will default to the Composite Estimator.
	*
	* <h4>Composite Estimator</h4>
	* This advanced estimator is a blend of several algorithms including new algorithms developed by Kevin Lang for his
	* Compressed Probabilistic Counting (CPC) sketch[4]. These algorithms provide near optimal estimation accuracy
	* for cases that don't qualify for HIP / Martingale estimation.
	*
	* <p>As a result of all of this work on accuracy, one will get a very smooth curve of the underlying accuracy of the
	* sketch once the statistical randomness is removed through multiple trials. This can be observed in the
	* following graph.</p>
	*
	* <p><img src="doc-files/HLL_HIP_K12T20U20.png" width="500" alt="HLL Accuracy">[6]</p>
	*
	* <p>The above graph has 7 curves. At y = 0, is the median line that hugs the x-axis so closely that it can't be seen.
	* The two curves, just above and just below the x-axis, correspond to +/- 1 standard deviation (SD) of error.
	* The distance between either one of this pair and the x-axis is also known as the Relative Standard Error (RSE).
	* This type of graph for illustrating sketch error we call a "pitchfork plot".</p>
	*
	* <p>The next two curves above and below correspond to +/- 2 SD, and
	* the top-most and bottom-most curves correspond to +/- 3 SD.
	* The chart grid lines are set at +/- multiples of Relative Standard Error (RSE) that correspond to +/- 1,2,3 SD.
	* Below the cardinality of about 512 there is no error at all. This is the point where this particular
	* sketch transitions from sparse to dense (or estimation) mode.</p>
	*
	* <h3>Three HLL Types</h3>
	* This HLL implementation offers three different types of HLL sketch, each with different
	* trade-offs with accuracy, space and performance. These types are selected with the
	* {@link org.apache.datasketches.hll.TgtHllType TgtHllType} parameter.
	*
	* <p>In terms of accuracy, all three types, for the same <i>lgConfigK</i>, have the same error
	* distribution as a function of cardinality.</p>
	*
	* <p>The configuration parameter <i>lgConfigK</i> is the log-base-2 of <i>K</i>,
	* where <i>K</i> is the number of buckets or slots for the sketch. <i>lgConfigK</i> impacts both accuracy and
	* the size of the sketch in memory and when stored.</p>
	*
	* <h4>HLL 8</h4>
	* This uses an 8-bit byte per HLL bucket. It is generally the
	* fastest in terms of update time but has the largest storage footprint of about <i>K</i> bytes.
	*
	* <h4>HLL 6</h4>
	* This uses a 6-bit field per HLL bucket. It is the generally the next fastest
	* in terms of update time with a storage footprint of about <i>3/4 * K</i> bytes.
	*
	* <h4>HLL 4</h4>
	* This uses a 4-bit field per HLL bucket and for large counts may require
	* the use of a small internal auxiliary array for storing statistical exceptions, which are rare.
	* For the values of <i>lgConfigK > 13</i> (<i>K</i> = 8192),
	* this additional array adds about 3% to the overall storage. It is generally the slowest in
	* terms of update time, but has the smallest storage footprint of about <i>K/2 * 1.03</i> bytes.
	*
	* <h3>Off-Heap Operation</h3>
	* This HLL sketch also offers the capability of operating off-heap. Given a <i>WritableMemory[5]</i> object
	* created by the user, the sketch will perform all of its updates and internal phase transitions
	* in that object, which can actually reside either on-heap or off-heap based on how it was
	* configured. In large systems that must update and union many millions of sketches, having the
	* sketch operate off-heap avoids the serialization and deserialization costs of moving sketches from heap to
	* off-heap and back, and reduces the need for garbage collection.
	*
	* <h3>Merging sketches with different configured <i>lgConfigK</i></h3>
	* This enables a user to union a HLL sketch that was configured with, say, <i>lgConfigK = 12</i>
	* with another loaded HLL sketch that was configured with, say, <i>lgConfigK = 14</i>.
	*
	* <p>Why is this important? Suppose you have been building a history of sketches of your customer's
	* data that go back a full year (or 5 or 10!) that were all configured with <i>lgConfigK = 12</i>. Because sketches
	* are so much smaller than the raw data it is possible that the raw data was discarded keeping only the sketches.
	* Even if you have the raw data, it might be very expensive and time consuming to reload and rebuild all your
	* sketches with a larger more accurate size, say, <i>lgConfigK = 14</i>.
	* This capability enables you to merge last year's data with this year's data built with larger sketches and still
	* have meaningful results.</p>
	*
	* <p>In other words, you can change your mind about what size sketch you need for your application at any time and
	* will not lose access to the data contained in your older historical sketches.</p>
	*
	* <p>This capability does come with a caveat: The resulting accuracy of the merged sketch will be the accuracy of the
	* smaller of the two sketches. Without this capability, you would either be stuck with the configuration you first
	* chose forever, or you would have to rebuild all your sketches from scratch, or worse, not be able to recover your
	* historical data.</p>
	*
	* <h3>Multi-language, multi-platform.</h3>
	* The binary structures for our sketch serializations are language and platform independent.
	* This means it is possible to generate an HLL sketch on a C++ Windows platform and it can be used on a
	* Java or Python Unix platform.
	*
	* <p>[1] Philippe Flajolet, et al, <a href="https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf">
	<i>HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.</i></a>
	* DMTCS proc. <b>AH</b>, 2007, 127-146.
	*
	* <p>[2] Edith Cohen, <a href="https://arxiv.org/pdf/1306.3284.pdf">
	<i>All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis.</i></a>
	* PODS'14, June 22-27, Snowbird, UT, USA.
	*
	* <p>[3] Daniel Ting,
	* <a href="https://research.facebook.com/publications/streamed-approximate-counting-of-distinct-elements">
	<i>Streamed Approximate Counting of Distinct Elements, Beating Optimal Batch Methods.</i></a>
	* KDD'14 August 24, 2014 New York, New York USA.
	*
	* <p>[4] Kevin Lang,
	* <a href="https://arxiv.org/abs/1708.06839">
	<i>Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm.</i></a>
	* arXiv 1708.06839, August 22, 2017, Yahoo Research.
	*
	* <p>[5] Memory Component,
	* <a href="https://datasketches.apache.org/docs/Memory/MemoryComponent.html">
	<i>DataSketches Memory Component</i></a>
	*
	* <p>[6] MacBook Pro 2.3 GHz 8-Core Intel Core i9
	*
	* @see org.apache.datasketches.cpc.CpcSketch
	*
	* @author Lee Rhodes
	* @author Kevin Lang
	*/
	package org.apache.datasketches.hll;