{'fraction_non_alphanumeric': 0.04317849548112706, 'fraction_numerical': 0.017759835194045722, 'mean_word_length': 4.52381389373222, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
SetSketch: Filling the Gap between MinHash and HyperLogLog

MinHash and HyperLogLog are sketching algorithms that have become indispensable for set summaries in big data applications. While HyperLogLog allows counting different elements with very little space, MinHash is suitable for the fast comparison of sets as it allows estimating the Jaccard similarity and other joint quantities. This work presents a new data structure called SetSketch that is able to continuously fill the gap between both use cases. Its commutative and idempotent insert operation and its mergeable state make it suitable for distributed environments. Fast, robust, and easy-to-implement estimators for cardinality and joint quantities, as well as the ability to use SetSketch for similarity search, enable versatile applications. The presented joint estimator can also be applied to other data structures such as MinHash, HyperLogLog, or HyperMinHash, where it even performs better than the corresponding state-of-the-art estimators in many cases.


INTRODUCTION
Data sketches [16] that are able to represent sets of arbitrary size using only a small, fixed amount of memory have become important and widely used tools in big data applications. Although individual elements can no longer be accessed after insertion, they are still able to give approximate answers when querying the cardinality or joint quantities which may include the intersection size, union size, size of set differences, inclusion coefficients, or similarity measures like the Jaccard and the cosine similarity.
Numerous such algorithms with different characteristics have been developed and published over the last two decades. They can be classified based on following properties [53] and use cases: Idempotency: Insertions of values that have already been added should not further change the state of the data structure. Even though this seems to be an obvious requirement, it is not satisfied by many sketches for sets [11,47,58,67,69].

Commutativity:
The order of insert operations should not be relevant for the final state. If the processing order cannot be guaranteed, commutativity is needed to get reproducible results. Many data structures are not commutative [13,32,65].
Mergeability: In large-scale applications with distributed data sources it is essential that the data structure supports the union set operation. It allows combining data sketches resulting from partial data streams to get an overall result. Ideally, the union operation is idempotent, associative, and commutative to get reproducible results. Some data structures trade mergeability for better space efficiency [11,13,65].
Space efficiency: A small memory footprint is the key purpose of data sketches. They generally allow to trade space for estimation accuracy, since variance is typically inversely proportional to the sketch size. Better space efficiencies can sometimes also be achieved at the expense of recording speed, e.g. by compression [21,36,62].
Recording speed: Fast update times are crucial for many applications. They vary over many orders of magnitude for different data structures. For example, they may be constant like for the HyperLogLog (HLL) sketch [30] or proportional to the sketch size like for minwise hashing (MinHash) [6].
Cardinality estimation: An important use case is the estimation of the number of elements in a set. Sketches have different efficiencies in encoding cardinality information. Apart from estimation error, robustness, speed, and simplicity of the estimation algorithm are important for practical use. Many algorithms rely on empirical observations [34] or need to combine different estimators for different cardinality ranges, as is the case for the original estimators of HLL [30] and HyperMinHash [72].
Joint estimation: Knowing the relationship among sets is important for many applications. Estimating the overlap of both sets in addition to their cardinalities eventually allows the computation of joint quantities such as Jaccard similarity, cosine similarity, inclusion coefficients, intersection size, or difference sizes. Data structures store different amounts of joint information. In that regard, for example, MinHash contains more information than HLL. Extracting joint quantities is more complex compared to cardinalities, because it involves the state of two sketches and requires the estimation of three unknowns in the general case, which makes finding an efficient, robust, fast, and easy-to-implement estimation algorithm challenging. If a sketch supports cardinality estimation and is mergeable, the joint estimation problem can be solved using the inclusion-exclusion principle | ∩ | = | | + | | − | ∪ |. However, this naive approach is inefficient as it does not use all information available.
Locality sensitivity: A further use case is similarity search. If the same components of two different sketches are equal with a probability that is a monotonic function of some similarity measure, it can be used for locality-sensitive hashing (LSH) [2,35,43,73], an indexing technique that allows querying similar sets in sublinear time. For example, the components of MinHash have a collision probability that is equal to the Jaccard similarity.
The optimal choice of a sketch for sets depends on the application and is basically a trade-off between estimation accuracy, speed, and memory efficiency. Among the most widely used sketches are MinHash [6] and HLL [30]. Both are idempotent, commutative, and mergeable, which is probably one of the reasons for their popularity. The fast recording speed, simplicity, and memory-efficiency have made HLL the state-of-the-art algorithm for cardinality estimation. In contrast, MinHash is significantly slower and is less memory-efficient with respect to cardinality estimation, but is locality-sensitive and allows easy and more accurate estimation of joint quantities.

Motivation and Contributions
The motivation to find a data structure that supports more accurate joint estimation and locality sensitivity like MinHash, while having a better space-efficiency and a faster recording speed that are both closer to those of HLL, has led us to a new data structure called SetSketch. It fills the gap between HLL and MinHash and can be seen as a generalization of both as it is configurable with a continuous parameter between those two special cases. The possibility to fine-tune between space-efficiency and joint estimation accuracy allows better adaptation to given requirements.
We present fast, robust, and simple methods for cardinality and joint estimation that do not rely on any empirically determined constants and that also give consistent errors over the full cardinality range. The cardinality estimator matches that of both MinHash or HLL in the corresponding limit cases. Together with the derived corrections for small and large cardinalities, which do not require any empirical calibration, the estimator can also be applied to HLL and generalized HyperLogLog (GHLL) sketches over the entire cardinality range. Since its derivation is much simpler than that in the original paper based on complex analysis [30], this work also contributes to a better understanding of the HLL algorithm.
The presented joint estimation method can be also specialized and used for other data structures. In particular, we derived a new closed-form estimator for MinHash that dominates the state-ofthe-art estimator based on the number of identical components. Furthermore, our approach is able to improve joint estimation from HLL, GHLL, and HyperMinHash sketches except for very small sets compared to the corresponding state-of-the-art estimators. Given the popularity of all those sketches, specifically of MinHash and HLL, these side results could therefore have a major impact in practice, as more accurate estimates can be made from existing and persisted data structures. We also found that a performance optimization actually developed for SetSketch can be applied to HLL to speed up recording of large sets.
The presented methods have been empirically verified by extensive simulations. For the sake of reproducibility the corresponding source code including a reference implementation of SetSketch is available at https://github.com/dynatrace-research/set-sketchpaper. An extended version of this paper with additional appendices containing mathematical proofs and more experimental results is also available [28].

MinHash
MinHash [6] maps a set to an -dimensional vector ( 1 , . . . , ) using Here ℎ are independent hash functions. The probability, that components and of two different MinHash sketches for sets and match, equals the Jaccard similarity This locality sensitivity makes MinHash very suitable for set comparisons and similarity search, because the Jaccard similarity can be directly and quickly estimated from the fraction of equal components with a root-mean-square error (RMSE) of MinHash also allows the estimation of cardinalities [12,13] and other joint quantities [15,19]. Meanwhile, many improvements and variants have been published that either improve the recording speed or the memory efficiency. One permutation hashing [40] reduces the costs for adding a new element from O ( ) to O (1). However, there is a high probability of uninitialized components for small sets leading to large estimation errors. This can be remedied by applying a finalization step called densification [44,63,64] which may be expensive for small sets [27] and also prevents further aggregations. Alternatively, fast similarity sketching [17], SuperMinHash [25], or weighted minwise hashing algorithms like BagMinHash [26] and ProbMinHash [27] specialized to unweighted sets can be used instead. Compared to one permutation hashing with densification, they are mergeable, allow further element insertions, and even give more accurate Jaccard similarity estimates for small set sizes.
To shrink the memory footprint, b-bit minwise hashing [39] can be used to reduce all MinHash components from typically 32 or 64 bits to only a few bits in a finalization step. Although this loss of information must be compensated by increasing the number of components , the memory efficiency can be significantly improved if precise estimates are needed only for high similarities. However, the need of more components increases the computation time and the sketch cannot be further aggregated or merged after finalization.

HyperLogLog
The HyperLogLog (HLL) data structure consists of integer-valued registers 1 , 2 , . . . , similar to MinHash. While MinHash typically uses at least 32 bits per component, HLL only needs 5-bit or 6-bit registers to count up to billions of distinct elements [30,34]. The state for a given set is defined by where ℎ are independent hash functions.
= 0 is used for initialization and the representation of empty sets. The original HLL uses the base = 2, which makes the logarithm evaluation very cheap. We refer to the generalized HyperLogLog (GHLL) when using any > 1 [12,53]. Definition (1) leads to a recording time of O ( ). Therefore, to have a constant time complexity, HLL implementations usually use stochastic averaging [30] which distributes the incoming data stream over all registers := max ∈ :ℎ 1 ( )= ⌊1 − log ℎ 2 ( )⌋, where ℎ 1 and ℎ 2 are independent uniform hash functions mapping to {1, 2, . . . , } and the interval (0, 1), respectively. Instead of using two hash functions, implementations typically calculate a single hash value that is split into two parts. The original cardinality estimator [30] was inaccurate for small and large cardinalities. Therefore, a series of improvements have been proposed [34,59,70], which finally ended in an estimator that does not require empirical calibration [23,24] and that is already successfully used by the Redis in-memory data store.
HLL is not very suitable for joint estimation or similarity search. The reason is that there is no simple estimator for the Jaccard similarity and no closed-form expression for the collision probability like for MinHash. The inclusion-exclusion principle gives significantly worse estimates for joint quantities than MinHash using the same memory footprint [18]. A maximum likelihood (ML) based method [23,24] for joint estimation was proposed, that performs significantly better, but requires solving a three-dimensional optimization problem, which does not easily translate into a fast and robust algorithm. A computationally less expensive method was proposed in [49] for estimating inclusion coefficients. However, it relies on precomputed lookup tables and does not properly account for stochastic averaging, which can lead to large errors for small sets.
These joint estimation approaches have proven that HLL also encodes some joint information. This might be one reason why HLL's asymptotic space efficiency, when considering cardinality estimation only, is not optimal [53,54]. Lossless compression [21,36,62] is able to improve the memory efficiency at the expense of recording speed and is therefore rarely used in practice. Approaches using lossy compression [69] are not recommended as their insert operations are not idempotent and commutative.
Nevertheless, due to its simplicity, HLL has become the stateof-the-art cardinality estimation algorithm, especially if the data is distributed. This is evidenced by the many databases like Redis, Oracle, Snowflake, Microsoft SQL Server, Google BigQuery, Vertica, Elasticsearch, Aerospike, or Amazon Redshift that use HLL under the hood to realize approximate distinct count queries. HLL is also used for many applications like metagenomics [1,22,46], graph analysis [4,55,56], query optimization [31], or fraud detection [10].

HyperMinHash
HyperMinHash [72] is the first approach to combine some properties of HLL and MinHash in one data structure. It can be seen as a generalization of HLL and one permutation hashing. Hyper-MinHash supports cardinality and joint estimation by using larger registers and hence more space than HLL. Unfortunately, the theoretically derived Jaccard similarity estimator is relatively complex and too expensive for practical use. Therefore, an approximation based on empirical observations was proposed. However, the original estimation approach is not optimal, as our results presented later have shown that even the naive inclusion-exclusion principle works better in some scenarios.
HyperMinHash with parameter is very similar to GHLL with base = 2 2 − . The reason is that HyperMinHash approximates the probability distribution of GHLL with probabilities that are just powers of 1 2 as shown in Figure 1. This has the advantage that hash values can be mapped to corresponding update values using only a few CPU instructions. Like those of HLL and GHLL, the register values of HyperMinHash are not locality-sensitive.

Further Related Work
A simple, though obviously not very memory-efficient, way to combine the properties of MinHash and HLL is to use them both in parallel [9,52]. Probably the best alternative to MinHash and HLL which also works for distributed data and which even supports HyperMinHash ( = 3) Figure 1: Probabilities of register update values for GHLL and HyperMinHash with equivalent configurations.
binary set operations is the ThetaSketch [18]. The downsides are a significantly worse memory efficiency compared to HLL in terms of cardinality estimation and that it is not locality-sensitive like MinHash.

METHODOLOGY
The basics of SetSketch follow directly from the properties introduced in Section 1. Similar to MinHash and HLL we consider a mapping from a set to integer-valued registers 1 , 2 , . . . , . Furthermore, we assume that register values are obtained through some hashing procedure and that they are identically distributed. Since we want to estimate the cardinality from the register values, the distribution of should only depend on the cardinality = | | Mergeability requires that the register value ∪ , of the union of two sets and can be computed directly from the corresponding individual register values and using some binary operation ∪ , = ( , ). To enable cardinality estimation, register values need to have some monotonic dependence on the cardinality. Without loss of generality, we consider nondecreasing monotonicity. Therefore, and because | ∪ | ≥ | | and | | ≥ | | ⇒ | ∪ | ≥ | ∪ |, we want to satisfy ( , ) ≥ and ≥ ⇒ ( , ) ≥ ( , ), respectively. The only binary operation with these properties and that is also idempotent and commutative, is the maximum function (see Lemma 1). Therefore, we require ∪ , = max( , ). For two disjoint sets and with cardinalities | | = and | | = we have | ∪ | = + . In this case and are independent and therefore ( ∪ , ≤ ) = (max( , ) ≤ ) = ( ≤ )· ( ≤ ) which results in a functional equation To allow estimation with constant relative error over a wide range of cardinalities, the location of the distribution should increase logarithmically with the cardinality , while its shape should remain essentially the same. For a discrete distribution this can be enforced by the functional equation Multiplying the cardinality with the constant > 1, which corresponds to an increment on the logarithmic scale, shifts the distribution to the right by 1.
The system of functional equations composed of (2) and (3) has the solution with some constant > 0 (see Lemma 2). For a set with a single element, in particular, this is Therefore, needs to be distributed as ∼ ⌊1 − log ⌋ where ∼ Exp( ) is exponentially distributed with rate . This directly leads to the definition of our new SetSketch data structure, which sets the state for a given set as (6) where ℎ ( ) are hash functions with exponentially distributed output. This definition is very similar to that of HLL without stochastic averaging (1) where the hash values are distributed uniformly instead of exponentially.

Ordered Register Value Updates
Updating SetSketch registers based on (6) is not very efficient, because processing a single element requires hash function evaluations and is typically in the hundreds or thousands. Therefore, Algorithm 1 uses an alternative method based on ideas from our previous work [25][26][27] to reduce the average time complexity for adding an element from O ( ) to O (1) for sets significantly larger than .
Since register values are increasing with cardinality, only the smallest hash values ℎ ( ) will be relevant for the final state according to (6). In particular, if low ≤ min( 1 , . . . , ) denotes some lower bound of the current state, only hash values ℎ ( ) ≤ − low will be able to alter any register. As more elements are added to the SetSketch, the register values increase and so does their common minimum, allowing low to be set to higher and higher values. For large sets, − low will eventually become so small that almost all hash values of further elements will be greater. Therefore, computing the hash values in ascending order would allow to stop the processing of an element after a hash value is greater than − low , and thus to achieve an asymptotic time complexity of O (1).
For that, we consider all hash values ℎ ( ) as random values generated by a pseudorandom number generator that was seeded with element . This perspective allows us to use any other random process that assigns exponentially distributed random values to each ℎ ( ). In particular, we can use an appropriate ascending random sequence 0 < 1 < 2 < . . . < whose values are randomly shuffled and assigned to ℎ 1 ( ), ℎ 2 ( ), . . . , ℎ ( ). Shuffling corresponds to sampling without replacement and can be efficiently realized as described in [26,27] based on the Fisher-Yates algorithm [29]. The random values must be chosen such that ℎ ( ) are eventually exponentially distributed as required by (6).
One possibility to achieve that is to use exponentially distributed spacings [20] In this way the final hash values ℎ ( ) will be statistically independent and the state of SetSketch will look like as if it was generated using independent hash functions. Alternatively, the domain of the exponential distribution with rate can be divided into intervals [ −1 , ) with 0 = 0 and = ∞. Setting := 1 log(1+ /( − )) ensures that an exponentially distributed random value ∼ Exp( ) has equal probability to fall into any of these intervals ( ∈ [ −1 , )) = 1 (see Lemma 3). Hence, if the points are sampled in ascending order according to where Exp( ; −1 , ) denotes the truncated exponential distribution with rate and domain [ −1 , ), the shuffled assignment will lead to hash values ℎ ( ) that are exponentially distributed with rate . However, in contrast to the first approach, the hash values ℎ ( ) will be statistically dependent, because there is always exactly one point sampled from each interval. This correlation will be less significant for large sets ≫ , where it is unlikely that one element is responsible for the values of different registers at the same time. Dependent on which method is used in conjunction with (6) to calculate the register values, we refer to SetSketch1 for the uncorrelated approach using exponential spacings and to SetSketch2 for the correlated approach using sampling from disjoint intervals.

Lower Bound Tracking
Different strategies can be used to keep track of a lower bound low as needed for an asymptotic constant-time insert operation. Since maintenance of the minimum of all register values with a small worst case complexity would require additional space by using either a histogram [23] or binary trees [26,27], we decided to simply update the lower bound regularly by scanning the whole register array as suggested in [61] which takes O ( ) time. However, since this approach is inefficient for small bases , Algorithm 1 counts the number of register modifications instead of the number of register values greater than the minimum. After every register updates when ≥ , low is updated and set to the current minimum of all register values, and is reset. By definition, this contributes at most amortized constant time to every register increment and hence does not change the expected time complexity.

Parameter Configuration
SetSketch has 4 parameters, , , , and , that need to be set appropriately. If we have registers, which are able to represent all values from {0, 1, 2, . . . , , + 1} with some nonnegative integer , the memory footprint will be ⌈log 2 ( + 2)⌉ bits without special encoding. determines the accuracy of cardinality estimates, because, as shown later, the RMSE is in the range [1/ √ , 1.04/ √ ] for ≤ 2. While the choice of the base has only little influence on cardinality estimation, joint estimation and locality sensitivity are significantly improved as → 1. The cardinality range, for which accurate estimation is possible, is controlled by the parameters and . Since the support of distribution (4) is unbounded, and need to be chosen such that register values smaller than 0 or greater than + 1 are very unlikely and can be ignored for the expected cardinality range. The lower bound of this range is typically 1 as we want SetSketches to be able to represent any set with at least one element. If we choose ≥ log( / )/ for some ≪ 1, it is guaranteed that negative register values occur only with a maximum probability of (see Lemma 4). Therefore, the error introduced by using zero as initial value as done in Algorithm 1 is negligible for small enough values of . In practice, setting = 20 is a good choice in most cases. Even in the extreme case with → 1 and = 2 20 , the probability is still less than 0.22 % to encounter at least one negative value. Similarly, setting ≥ ⌊log max ⌋ guarantees that register values greater than + 1 occur only with a maximum probability of for all cardinalities up to max (see Lemma 5). A small implies a larger value of and therefore also a larger memory footprint, if the cardinality range is fixed.
To give a concrete example, consider a SetSketch with parameters = 4096, = 1.001, = 20, and = 2 16 − 2 = 65534. The last parameter ensures that two bytes are sufficient to represent a single register and the whole data structure takes 8 kB. The probability that there is at least one register with negative value is 8.28 × 10 −6 for a set with just a single element. Furthermore, the probability that any register value is greater than + 1 is 2.93 × 10 −6 for = 10 18 . Therefore, a SetSketch using this configuration is suitable to represent any set with up to 10 18 distinct elements. The expected error of cardinality estimates is approximately 1/ √ ≈ 1.56 %.

ESTIMATION
In this section we present methods for cardinality and joint estimation. We will assume that register values are statistically independent which is only true for SetSketch1 and only a good approximation for SetSketch2 in the case of large sets with ≫ . However, our experiments presented later have shown that the estimators derived under this assumption also perform well for SetSketch2 over the entire cardinality range. The correlation even has a positive effect and reduces the estimation errors for small sets. We introduce some special functions and corresponding approximations that are used for the derivation of the estimators. The functions 1 ( ) and 2 ( ) defined by where Γ denotes the gamma function, are both very close to 1 for ≤ 2 (see Lemma 8 and Lemma 10). For = 2 we have max | 1 ( ) − 1| ≤ 10 −5 and max | 2 ( ) − 1| ≤ 10 −4 , which shows that these approximations introduce only a small error. Smaller values of lead to even smaller errors as both functions converge quickly towards 1 as → 1. Another approximation that we will use is The relative error | | is smaller than 10 −5 for = 2 and approaches zero quickly as → 1 (see Lemma 11).

Cardinality Estimation
Instead of using the straightforward way of estimating the cardinality using the ML method based on (4), we derive a closed-form estimator, based on our previous work [23,24], that is simpler to implement, cheaper to evaluate, and gives almost identical results. The expectation of ( − ) with ∈ {1, 2} and distributed according to (4) is given by Here the asymptotic identity (9) was used as approximation in the final step. We now consider the statistic = log − . Using (11) for the cases = 1 and = 2 we get for its expectation and its variance (see Lemma 12) The delta method [8] gives for → ∞ E( −1 ) ≈ and Var( −1 ) ≈ 2 +1 −1 log( ) − 1 which suggests to use −1 as estimator for the cardinalitŷ This estimator can be quickly evaluated, if the powers of are precalculated and stored in a lookup table for all possible exponents which are known to be from {0, 1, . . . , + 1}. The corresponding relative standard deviation (RSD) √︁ . It is minimized for → 1, where it equals 1/ √ , and increases slowly with . For = 2 the expected error is still as low as 1.04/ √ . However, as already discussed, smaller values of require larger values of and hence more space.
Optimal memory efficiency, measured as the product of the variance and the memory footprint, is typically obtained for values of ranging from 2 to 4. Theoretically, if register values are compressed, a better memory efficiency can be achieved for → ∞ [53]. Values significantly greater than 2 invalidate the approximation (9) which was used for the derivation of estimator (12). To reduce the estimation error in this regime, random offsets, which correspond to register-specific values of parameter , would be necessary [42,53]. This work, however, focuses on ≤ 2. Although small values of are inefficient for cardinality estimation, they contain, as we will show, more information about how sets relate to each other, which ultimately justifies slightly larger memory footprints.

Joint Estimation
The relationship of two sets and can be characterized by three quantities. Without loss of generality we choose the cardinalities = | |, = | |, and the Jaccard similarity = | ∩ | | ∪ | with the natural constraint ∈ [0, min( , )] for parameterization. Other quantities such as can be expressed in terms of only these three variables. If we have two SetSketches representing two different sets, we would like to find estimates for , , and , which would allow us to estimate any other quantity of interest. While we can use the cardinality estimator derived in the previous section to get estimates for and , respectively, the estimation of is more challenging. One possibility is to leverage the mergeability of data sketches and use the inclusion-exclusion principle. Assume^,^, and^∪ are cardinality estimates of | |, | |, and | ∪ |, respectively. Then the inclusion-exclusion principle allows estimating the intersection size as^+^−^∪ . This can be used to estimate aŝ To ensure the natural constraint ∈ [0, min( , )] and the nonnegativity of estimated intersection and difference sizes, it might be necessary to trim^i n-ex to the range [0, min(^/^,^/^)].
In the following a new joint estimation approach is derived that dominates the inclusion-exclusion principle as our experiments have shown. Using (4), the joint cumulative distribution function of registers and of two SetSketches representing sets and , respectively, is given by ≤ . It can be used to calculate the probability that Here we used the approximation (10) which is asymptotically equal as → 1 and introduces a negligible error if ≤ 2. is defined as where we introduced the relative cardinalities = + and = + with + = 1. The approximation of ( = ) is also always nonnegative (see Lemma 13).
If the cardinalities and are known, the ML method can be used to estimate . The corresponding log-likelihood function as function of using the approximated probabilities is where + := |{ : > }|, − := |{ : < }|, and 0 := |{ : = }| are the number of registers in the sketch of that are greater than, less than, or equal to those in the sketch of , respectively. Since this log-likelihood function is cheap to evaluate requiring only 5 logarithm evaluations and is strictly concave on the domain ∈ [0, min( , )] = [0, min( , )] at least for all ≤ ≈ 2.718 (see Lemma 14), the ML estimate for can be quickly and robustly found using standard univariate optimization algorithms like Brent's method [5].
Since the ML estimator is asymptotically efficient, the RMSE of the ML estimate is expected to be equal to −1/2 ( ) as → ∞.
( ) denotes the Fisher information with respect to for known cardinalities and , which can be derived as (see Lemma 15) The asymptotic RMSE can be compared with the Jaccard estimator of MinHash for which the RMSE is √︁ (1 − )/ . The corresponding ratio is shown in Figure 2 for the cases = and = 0.5 , and various values of . For = the curves approach 1 as → 1. If = 1.001 the difference from 1 is already very small and hence the estimation error for will be almost the same as for MinHash with the same number of registers . Given that 2-byte registers are sufficient for = 1.001 as discussed in Section 2.3, this significantly improves the space efficiency compared to MinHash which uses 4-or even 8-byte components. As shown in Figure 2 for = 0.5 , the error can be even smaller than that of the MinHash Jaccard estimator. The reason is that our estimation approach incorporates and and also if register values are greater or smaller while the classic MinHash estimator only considers the number of equal registers.
If the true cardinalities and are not known, we simply replace them by corresponding estimates^and^using (12). As a consequence, the RMSE will apparently increase and −1/2 ( ) will only represent an asymptotic lower bound as → ∞. Nevertheless, as supported by our experiments presented later, the estimation error is indistinguishable from the case with known cardinalities if the sets have equal size, thus if = . The reason is that + and − are identically distributed in this case, which makes the log-likelihood function symmetric with respect to and . Since this also implies = = 1 2 and estimates^=^/(^+^) and =^/(^+^) for and satisfy^+^= 1 by definition, they can be written as^= 1 2 + and^= 1 2 − , respectively, with some estimation error . Therefore and due to the symmetry of the loglikelihood function, the ML estimator is an even function of . The estimated Jaccard similarity will therefore differ only by an O ( 2 ) term from the estimate based on the true cardinalities and . Since ≪ 1 for sufficiently large , this second order term can be ignored in practice.

Locality Sensitivity
A collision probability, that is a monotonic function of some similarity measure, is the foundation of LSH [2,35,43,73]. Rewriting of (14) and using + = 1 gives for the probability of a register to be equal in two different SetSketches . ).
These bounds are illustrated in Figure 3 for ∈ {2, 1.2, 1.001}. They are very tight for large . Both bounds approach ( = ) = as → 1. Estimating ( = ) by 0 / and resolving for results in corresponding lower and upper bound estimatorŝ The tight boundaries, especially for large , make SetSketch an interesting alternative to MinHash for LSH. Like b-bit minwise hashing [39] and odd sketches [47], SetSketches are more memory efficient than MinHash, but unlike them, SetSketches can be further aggregated. The RMSE of MinHash is √︁ (1 − )/ . As long as the RMSE of SetSketch is not significantly greater than that, the additional error from using SetSketches instead of MinHash is negligible. For comparison, we consider the worst case scenario with | | = | | ⇔ = = 1 2 , which maximizes the collision probability, while using^u p , which is based on the minimum possible collision probability, for estimation. Figure 4 shows the theoretical results for different values of and . Even for large values like = 2 the RMSE is only increased by less than 20%, for all similarities greater than 0.7 or 0.9 for the cases = 256 and = 4096, respectively. The difference becomes smaller with decreasing . The RMSE almost matches that of MinHash for = 1.001, for which 2-byte registers suffice as mentioned earlier, again showing great potential for space savings compared to MinHash.
When searching for nearest neighbors with LSH, a set of candidates is determined first, which is then further filtered. For filtering, the presented more precise joint estimation approach can be used instead of (15) to reduce the false positive rate.

COMPARISON
This section compares MinHash and HLL with SetSketch, and in particular shows that they relate to SetSketches with = 1 and = 2, respectively.

MinHash
MinHash can be regarded as an extreme case of SetSketch1 with → 1 for which the statistic − − approaches a continuous uniform distribution according to (5). Therefore, since the registers of SetSketch1 are also statistically independent, the transformation ′ = 1 − − − makes SetSketch1 equivalent to MinHash with values ′ as → 1. Applying this transformation to (12) for → 1 and using lim →1 (1 − 1/ )/log( ) = 1 indeed leads to the cardinality estimator of MinHash [12,13] The presented joint estimation method can also be applied to MinHash. However, as MinHash uses the minimum instead of the maximum for state updates we have to redefine + and − as + := |{ : ′ < ′ }|, − := |{ : ′ > ′ }|. For → 1, the ML estimate can be explicitly expressed as (see Lemma 18) 7 and has an asymptotic RMSE of (see Lemma 19) This shows that this estimator outperforms the state-of-the-art Jaccard estimator, which has a RMSE of √︁ (1 − )/ . Our experiments showed that this estimator also works better, if the cardinalities are unknown and need to be estimated using (17). Therefore, this approach is a much less expensive alternative to the ML approach described in [15], which considers the full likelihood as a function of all 3 parameters and requires solving a three-dimensional optimization problem.
The state of SetSketch2 is logically equivalent to that of Super-MinHash as → 1. SuperMinHash also uses correlation between components and is able to reduce the variance of the standard estimator for by up to a factor of 2 for small sets [25].

HyperLogLog
The generalized HyperLogLog (GHLL) with stochastic averaging, which includes HLL as a special case with = 2, is similar to SetSketch with = 1/ . Under the Poisson model [23,30], which assumes that the cardinality is not fixed but Poisson distributed with mean , the register values will be distributed as ( ≤ ) = − −1 − for ≥ 0 (see Lemma 20). Comparison with (4) shows that the register values of GHLL are distributed as those of SetSketch for = 1/ and = provided that all register values are nonzero. Therefore, the cardinality estimator (12) can be used to estimate in this case. An unbiased estimator for the Poisson parameter is also an unbiased estimator for the true cardinality (see Lemma 21). Since (12) is asymptotically unbiased as → ∞, it can be used to estimate . And indeed, (12) corresponds to the cardinality estimator with a RSD of √︁ 3 log(2) − 1/ √ ≈ 1.04/ √ presented in [30] for HLL with base = 2.
For small cardinalities, when many registers are zero, the value distribution will differ significantly from (4) and the estimator will fail. However, it can be fixed by applying the same trick as presented for the case = 2 in [23]. If registers values are limited to the range The functions and are defined as converging series corr also includes a correction for very large cardinalities, for which register update values greater than + 1, exceeding the value range of registers, are more likely to occur. The corrected estimator could also be applied to misconfigured SetSketches that do not allow to ignore the probability of registers with values less than 0 or greater than + 1 as discussed in Section 2.3. To save computation time, the values of ( 0 / ) and ( +1 / ) can be tabulated for all possible values of 0 , +1 ∈ {0, 1, . . . , } for fixed and .
Due to the similarity of the register value distribution, the proposed joint estimation method also works well for GHLL, provided that all register values are from {1, 2, . . . , }. Since the estimator relies only on the relative order, it can be even applied as long as there are no registers having value 0 or +1 simultaneously in both GHLL sketches. Registers equal to + 1 can be easily avoided by choosing sufficiently large. Registers, that have never been updated and thus are zero in both sketches, are expected for union cardinalities | ∪ | smaller than , where := =1 1/ is the -th harmonic number. This follows directly from the coupon collector's problem [48]. If the registers do not satisfy the prerequisites for applying the new estimation approach, the inclusion-exclusion principle (13) could still be used as fallback.

HyperMinHash
The similarity with GHLL as discussed in Section 1.4 allows using the proposed joint estimation approach for HyperMinHash as well. If the condition of not too small cardinalities is satisfied, the experiments presented below have shown that the new approach also outperforms the original estimator of HyperMinHash, especially when the cardinalities of the two sets are very different.

EXPERIMENTS
For the sake of reproducibility, we used synthetic data for our experiments to verify SetSketch and the proposed estimators. The wide and successful application of MinHash, HLL, and many other probabilistic data structures has proven that the output of high-quality hash functions [66] is indistinguishable from uniform random values in practice. This justifies to simply use sets consisting of random 64-bit integers for our experiments. In this way arbitrary many random sets of predefined cardinality can be easily generated, which is fundamental for the rigorous verification of the presented estimators. Real-world data sets usually do not include thousands of different sets with the same predefined cardinality.

Implementation
Both SetSketch variants as well as GHLL have been implemented in C++. The corresponding source code, including scripts to reproduce all the presented results, has been made available at https: //github.com/dynatrace-research/set-sketch-paper. We used the Wyrand pseudorandom number generator [71] which is extremely fast, has a state of 64 bits, and passes a series of statistical quality tests [38]. Seeded with the element of a set, it is able to return a sequence of 64-bit pseudorandom integers. The random bits are used very economically. Only if all 64 bits are consumed, the next bunch of 64 bits will be generated. Sampling with replacement was realized as constant-time operation as described in [27] based on Fisher-Yates shuffling [29]. The algorithm proposed in [37] was used to sample random integers from intervals. The ziggurat method [45] as implemented in the Boost.Random C++ library [68] was used to obtain exponentially distributed random values. The algorithm described in [27] was applied to efficiently sample from a truncated exponential distribution as needed for SetSketch2. Our implementation precalculates and stores all relevant powers of −1 in a sorted array, which is then used to find register update values as defined by (6) using binary search instead of expensive logarithm evaluations. This also allows to limit the search space to values greater than low , which further saves time with increasing cardinality.

SetSketch1
SetSketch2 GHLL expected Figure 5: The relative bias, the relative RMSE, and the kurtosis of^ (12) for SetSketch1 and SetSketch2 and of^c orr (18) for GHLL.

Cardinality Estimation
Our cardinality estimation approach was tested by running 10 000 simulation cycles for different SetSketch and GHLL configurations.
In each cycle we generated 10 million 64-bit random integer values and inserted them into the data structure. The use of 64 bits makes collisions very unlikely and allows regarding the number of inserted random values as the cardinality of the recorded set. During each simulation cycle the cardinality was estimated for a predefined set of true cardinality values which have been chosen to be roughly equally spaced on the log-scale. We investigated SetSketch1, SetSketch2, and GHLL with stochastic averaging using = 256 and = 4096 registers. We considered different bases = 1.001 and = 2, for which we used 6-bit ( = 62) and 2-byte registers ( = 2 16 − 2 = 65534), respectively. For both SetSketch variants, we used = 20 and (12) for cardinality estimation. The corrected estimator (18) was used for GHLL. Figure 5 shows the relative bias, the relative RMSE, and the kurtosis of the cardinality estimates over the true cardinality. The bias is significantly smaller than the RMSE in all cases. Furthermore, when comparing = 256 and = 4096, the bias decreases more quickly than the RMSE as → ∞. Hence, the bias can be ignored in practice for reasonable values of .
The independence of register values in SetSketch1 leads to a constant error over the entire cardinality range, that matches well with the theoretically derived RSD from Section 3.1. In accordance with the discussion in Section 3.1, the error is only marginally improved when decreasing from 2 to 1.001. The error curves of SetSketch2 and GHLL are very similar and show a significant improvement for cardinalities smaller than . This is attributed to the correlation of register values of SetSketch2 and the stochastic averaging of GHLL, respectively, both of which have a similar positive effect. However, when comparing the kurtosis, which is expected to be equal to 3 for normal-like distributions, we observed huge values for GHLL. This means that GHLL is very susceptible to outliers for small cardinalities. This is not surprising, as stochastic averaging only updates a single register per element. For a set with cardinality = 2, for example, it happens with 1/ probability that both elements update the same register, which makes the state indistinguishable from that of a set with just a single element and obviously results in a large 50 % error. We also tested the ML method for cardinality estimation and obtained visually almost identical results (see Figure 12) which are therefore omitted in Figure 5 and which prove the efficiency of estimators (12) and (18).

Joint Estimation
To verify the presented joint estimation approach, we generated many pairs of random sets with predefined relationship. Each pair of sets ( , ) was constructed by generating three sets 1 , 2 , and 3 of 64-bit random numbers with fixed cardinalities 1 , 2 , and 3 , respectively, which are merged according to = 1 ∪ 3 and = 2 ∪ 3 . The use of 64-bit random numbers allows ignoring collisions and all three sets can be considered to be distinct. By construction, we have = 3 1 + 2 + 3 , = 1 + 3 , and = 2 + 3 , which guarantees both cardinalities, the Jaccard similarity, and hence also other joint quantities to be the same for all generated pairs ( , ). After recording both sets using the data structure under consideration and applying the proposed joint estimation approach, we finally compared the estimates with the prescribed true values for various joint quantities. Figure 6 shows the relative RMSE when estimating the Jaccard similarity, cosine similarity, inclusion coefficients, intersection size, and difference sizes using different approaches from SetSketch1 with = 20 and ∈ {1.001, 2}. The union cardinality was fixed | ∪ | = 10 6 and the Jaccard similarity was selected from ∈ {0.01, 0.1, 0.5}. Each data point shows the result after evaluating 1000 pairs of randomly generated sets. The charts were obtained by varying the ratio | \ |/| \ | over [10 −3 , 10 3 ] while keeping and | ∪ | fixed. The symmetry allowed us to perform the experiments only for ratios from [1, 10 3 ]. Figure 6 clearly shows that the proposed joint estimator dominates the inclusion-exclusion principle for all investigated joint quantities. The difference is more significant for small set overlaps like for = 0.01. Comparing the results for = 1.001 and = 2 shows that joint estimation can be significantly improved when using smaller bases . Knowing the true values of and further reduces the estimation error for which we observed perfect agreement with the theoretically derived RMSE. If and are known, any other joint quantity can be expressed as a function of . The corresponding ML estimate is therefore given bŷ = (^). Variable transformation of the Fisher information given in Section 3.2, allows to calculate the corresponding asymptotic RMSE of which is −1/2 ( )| ′ ( )| as → ∞. As also predicted for the case = , the estimation error of is the same regardless of whether the true cardinalities are known or not.       When running the same simulations for SetSketch2 and GHLL also with bases ∈ {1.001, 2}, we got almost identical charts (see Figure 13 and Figure 14), which therefore have been omitted here. The reason why our estimation approach also worked for GHLL is that the union cardinality was fixed at 10 6 which is large enough to not have any registers that are zero in both sketches as discussed in Section 4.2. In particular, this shows that our approach can significantly improve joint estimation from HLL sketches with = 2 for which the inclusion-exclusion principle is the state-of-the-art approach for joint estimation.
We repeated all simulations with a fixed union cardinality of | ∪ | = 10 3 . For SetSketch1, we obtained the same results as for | ∪ | = 10 6 (see Figure 15). However, the errors for SetSketch2 shown in Figure 7 are significantly smaller and also lower than theoretically predicted. The reason for this improvement is, as before for cardinality estimation, the statistical dependence between register values in case of small sets. For = 1.001, the error is reduced by a factor of up to √ 2 when estimating the Jaccard similarity using our new approach. This is expected as SetSketch2 corresponds to SuperMinHash [25] as → 1, for which the variance is known to be approximately 50% smaller than for MinHash, if | ∪ | is smaller than . Our joint estimator failed for GHLL in this case (see Figure 16), because | ∪ | = 10 3 is significantly smaller than with = 4096, and hence, the condition for its applicability is not satisfied as discussed in Section 4.2.
We also applied the new approach to MinHash and used the explicit estimation formula (17). Figure 8 only shows the results for | ∪ | = 10 6 , because the results are very similar for | ∪ | = 10 3 , as expected (see Figure 17). The results are also almost indistinguishable from those obtained for SetSketch with = 1.001 shown in Figure 6. Thus, SetSketch is able to give almost the same estimation accuracy using significantly less space as 2-byte registers are sufficient for = 1.001. We also analyzed the state-of-the-art MinHash estimator based on the fraction of equal components. For the case that the cardinalities are not known, they have been estimated using (16). Our new estimator has a significantly better overall performance in both cases with known and unknown cardinalities, respectively. Only for inclusion coefficients and difference sizes the original method led to a slightly smaller error for = 0.5 and | \ |/| \ | > 1. However, the new estimator clearly dominated, if sets have a small overlap. In contrast to the original estimator, it also dominates the inclusion-exclusion principle in all cases. Finally, due to its similarity to GHLL for which our approach was able to improve joint estimation, we also considered HyperMinHash. Figure 9 shows the results for a HyperMinHash with parameter = 10 which corresponds to a base of = 2 −2 10 ≈ 1.000677 as discussed in Section 1.4. The original estimator of HyperMin-Hash led to similar results as the original estimator of MinHash (compare Figure 8). In contrast to the original estimator, which is based on empirically determined constants, our approach is solely based on theory and never performed worse than the inclusionexclusion principle. Furthermore, since the estimation error was significantly reduced in many cases, our estimator seems to be superior to the original estimation approach. The results for the case that the cardinalities are known show perfect agreement with the theoretical RMSE originally derived for SetSketch1. Therefore, at least for large sets, HyperMinHash seems to encode joint information equally well as SetSketch with corresponding base. However, the big advantage of SetSketch is that the same estimator can be applied for any cardinalities, while estimation from GHLL or Hy-perMinHash sketches requires special treatment of small sets. The original HyperMinHash estimator delegates to a second estimator in this case.

Performance
The runtime behavior of a sketch is crucial for its practicality. Therefore, we measured the recording time for sets with cardinalities up to 10 7 . Instead of generating a set first, we simply generated 64-bit random numbers on the fly using the very fast Wyrand generator [71]. As hashing of more complex items is usually more expensive than generating random values, this experimental setup amplifies the runtime differences compared to reality, where elements also need to be loaded from main memory. Furthermore, we excluded initialization costs, which are comparable for all considered data structures and which are a negligible factor for large cardinalities. For each cardinality considered, we performed 1000 simulation runs. In each run, we measured the time needed to generate the corresponding number of random elements and to insert them into the data structure. Afterwards, we calculated the average recording time per element. We measured the performance for SetSketch1, SetSketch2, GHLL with ∈ {1.001, 2}, MinHash, and HLL and sketch sizes ∈ {256, 4096} on a Dell Precision 5530 notebook with an Intel Core i9-8950HK processor. Figure 10 summarizes the results. The recording speed was roughly independent of the set size for HLL and GHLL due to stochastic averaging. We also implemented variants of both algorithms that use lower bound tracking as described in Section 2.2. If update values are not greater than the current lower bound, they will not be able to change any register. This can avoid many relatively costly random accesses to individual registers. This optimization, which is simpler than other approaches [23,61], led to a significant performance improvement for HLL and GHLL with = 2 at large cardinalities. However, this optimization did not speed up recording for GHLL with = 1.001, because the calculation of register update values is the bottleneck here as it is more expensive for small .
For MinHash the recording time was also independent of the cardinality, but many orders of magnitude slower due to its O ( ) insert operation, which was also the reason why we only simulated sets up to a size of 10 5 . The insert operations of both SetSketch variants have almost identical performance characteristics. As expected, insertions are quite slow for small sets. However, with increasing cardinality, the tracked lower bound low will also increase and finally leads to better and better recording speeds. For large sets, SetSketch is several orders of magnitude faster than MinHash and SetSketch2 even achieves the performance of the non-optimized (without lower bound tracking) versions of HLL and GHLL. We observed a quicker decay for = 1.001 than for = 2. The reason is that register values are updated more frequently for smaller , which allows low to be raised earlier.

CONCLUSION
We have presented a new data structure for sets that combines the properties of MinHash and HLL and allows fine-tuning between estimation accuracy and memory efficiency. The presented estimators for cardinality and joint quantities do not require empirical calibration, give consistent errors over the full cardinality range without having to consider special cases such as small sets, and can be evaluated in a numerically robust fashion. The simple estimation from SetSketches, plus locality sensitivity as a bonus, compensate for the slower recording speed compared to HLL and GHLL for small sets. The developed joint estimator can also be straightforwardly applied to existing MinHash, HLL, GHLL, and HyperMinHash data structures to obtain more accurate results for joint quantities than with the corresponding state-of-the-art estimators in many cases. We expect that our estimation approach will also work for other set similarity measures or joint quantities that have not been covered by our experiments. with 1 ≤ ≤ is equal to 1 .
Proof. Using the cumulative distribution function of the exponential distribution ( < ) = 1 − − we get □ Lemma 4. If ≥ log( / )/ with > 0, the probability, that any register value of a SetSketch representing some nonempty set is negative, is bounded by , hence (min < 0) ≤ . Proof. By definition, the register values are smallest when the data structure represents just a set with a single element. Therefore, and because ≥ log( / )/ ⇔ − ≤ it is sufficient to show that (min < 0 | = 1) ≤ − holds for SetSketch1 and SetSketch2.
For a set with cardinality max the probability that max > + 1 can therefore be bounded by (max where Γ denotes the gamma function. Proof. The periodicity follows directly from ( ) = ( + 1). Therefore, the Fourier series can be written as Proof. We use induction. The case = 1 is trivial. Assume that the inequality holds for = , which is used together with 1 ≤ tanh( ) to prove the inequality for = + 1: For = 2 the right-hand side is less than 9.885 × 10 −6 . Since 2 ) which shows the rapid decay of the deviation from 1 as → 1 (see Figure 11). Therefore, 1 ( ) is well approximated by the constant 1 for not too large values of , especially for ≤ 2.
Proof. We use the Fourier series of 1 (Lemma 6), the identity |Γ(1 − i)| 2 = sinh( ) , and Lemma 7: Here we used the closed-form formula ∞ Proof. The case = 1 is trivial. For ≥ 2 we have For = 2 the right-hand side is less than 9.015 × 10 −5 . Since 2 ) which shows the rapid decay of the deviation from 1 as → 1 (see Figure 11). Therefore, 2 ( ) is well approximated by the constant 1 for not too large values of , especially for ≤ 2.
Proof. ≤ √ 2 implies 4 2 log 2 ≥ 2. Furthermore, we use the identity |Γ(2 − i)| 2 = (1 + 2 ) sinh( ) , Lemma 7, and Lemma 9: The geometric series converges, because log > 0. The numerator + 3 /6 is obviously smaller than sinh as it corresponds to the first two terms of the Taylor series of the hyperbolic sine function. □ Lemma 11. The relative difference of the function As this is the same upper bound as in Lemma 8, the relative error is also smaller than 9.885 × 10 −6 for ≤ 2 and quickly approaches zero as → 1.
Proof. The mean value theorem and Lemma 8 yield Proof. Proof. We show that all three terms are strictly concave themselves. For the first two terms, it is sufficient to show that the 16 function ( ) = log( ( )) is strictly concave on ∈ [0, 1). The second derivative is which is negative for all ∈ (0, 1) as long as log(1 − −1 ) , which is obviously the case for ≤ . The last term is log( ( )) with Proof.
Setting the first derivative of log L ( ) equal to 0 gives (log L ( )) ′ = + − + − − + 0 1 = 0, which can be transformed into the quadratic equation when using Using the quadratic formula, the smaller solution is given bŷ For this solution the following inequalities hold which shows that the smaller solution satisfies^∈ (0, min( , )).
Since we know that the solution is unique,^is indeed the searched solution.
The cases for which at least one of − , + , 0 is zero, need separate treatment. However, it is easy to verify that the above formula for^also holds for those special cases.
where we used + = 1 multiple times. □ Lemma 20. If the cardinality is not fixed, but follows a Poisson distribution with mean , hence ∼ Poisson( ), nonzero register values of a GHLL sketch using stochastic averaging will be distributed as the register values of a SetSketch with parameter = 1/ representing a set with cardinality .
Proof. Stochastic averaging means that each distinct element is used for updating only a single register. Since the number of distinct elements is Poisson distributed with mean , the number of elements for updating one particular register is also Poisson distributed with mean −1 where is the number of registers. For GHLL the update value update is distributed as update ∼ ⌊1 − log ℎ 2 ( )⌋ with ℎ 2 ( ) ∼ Uniform(0, 1) (see Section 1.3). The corresponding cumulative distribution function is given by As a consequence, the cumulative distribution function of some register value that is updated with a frequency that is Poisson distributed with mean −1 and probability mass ! is given by where we used the identity = ∞ =0 ! . Comparing ( ≤ ) = − −1 − with (4) completes the proof. □ Lemma 21. Assume the distribution of some discrete statistic depends on some parameter , which is Poisson distributed with mean , hence ∼ Poisson( ). Furthermore, assume that is an unbiased estimator for for all > 0, hence E( | ) = . Then, is also an unbiased estimator for , if is conditioned on , hence E( | ) = for all ≥ 0. Proof.
This power series with respect to is zero for all > 0 only if all coefficients are zero, which implies E( | ) = and shows that is an unbiased estimator for . □

B CORRECTED CARDINALITY ESTIMATOR
The derivation of cardinality estimator (12) assumed that register values are distributed according to (4 where * is distributed according to (4), hence Obviously, knowing * would still allow using the cardinality estimator (12) where * := |{ : * = }| is the histogram of values * . Hence, knowing the histogram * would be sufficient. Due to (19), this histogram relates to the observed histogram := |{ : Therefore, * is known for 1 ≤ ≤ and we just need to find a way to estimate * for all ≤ 0 and ≥ + 1 so that we can use (21). For ≤ 0, the identity which directly follows from (20), suggests that the estimates^ * for * should satisfy Similarly, for ≥ + 1, the identity which also follows from (20), leads to This system of equations with ≥ + 1 has the solution Complemented by the trivial estimator for the case 1 ≤ ≤ * = * = , the estimator for the whole histogram can be written Using these estimates instead of * in (21) giveŝ We used the identity ( − 1) ∞