Module hash4j
Package com.dynatrace.hash4j.distinctcount

Class HyperLogLog

java.lang.Object
com.dynatrace.hash4j.distinctcount.HyperLogLog
public final class HyperLogLog extends Object
A HyperLogLog implementation for approximate distinct counting.

Prefer using UltraLogLog which is more space-efficient.

This HyperLogLog (Flajolet2007) implementation uses 6 bits per register as proposed in (Heule2013).

See:

  • Flajolet, Philippe, et al. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." Discrete Mathematics and Theoretical Computer Science. Discrete Mathematics and Theoretical Computer Science, 2007.
  • Heule, Stefan, Marc Nunkesser, and Alexander Hall. "Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm." Proceedings of the 16th International Conference on Extending Database Technology. 2013.

  • Field Details

    • CORRECTED_RAW_ESTIMATOR

      public static final HyperLogLog.Estimator CORRECTED_RAW_ESTIMATOR
      Bias-reduced version of the standard HyperLogLog estimator using small range and large range correction as described in (Ertl2017).

      See:

      • Ertl, Otmar. "New cardinality estimation algorithms for HyperLogLog sketches." arXiv preprint arXiv:1702.01284 (2017).

    • MAXIMUM_LIKELIHOOD_ESTIMATOR

      public static final HyperLogLog.Estimator MAXIMUM_LIKELIHOOD_ESTIMATOR
      A bias-reduced version of the maximum-likelihood estimator described in (Ertl2017).

      See:

      • Ertl, Otmar. "New cardinality estimation algorithms for HyperLogLog sketches." arXiv preprint arXiv:1702.01284 (2017).

    • DEFAULT_ESTIMATOR

      public static final HyperLogLog.Estimator DEFAULT_ESTIMATOR
      The default estimator.

  • Method Details

    • create

      public static HyperLogLog create(int p)
      Creates an empty HyperLogLog sketch with given precision.

      The precision parameter p must be in the range {3, 4, 5, ..., 25, 26}. It also defines the size of the internal state, which is a byte array of length 2^p.

      Parameters:
      p - the precision parameter
      Returns:
      the new sketch
      Throws:
      IllegalArgumentException - if the precision parameter is invalid

    • create

      public static HyperLogLog create(UltraLogLog ullSketch)
      Creates a HyperLogLog sketch from an UltraLogLog sketch with same precision.

      The state of the resulting HyperLogLog sketch is the same as if all elements inserted into the UltraLogLog sketch had been inserted directly into the HyperLogLog sketch.

      Parameters:
      ullSketch - an UltraLogLog sketch
      Returns:
      a HyperLogLog sketch

    • wrap

      public static HyperLogLog wrap(byte[] state)
      Returns a HyperLogLog sketch whose state is kept in the given byte array.

      The array must have a length that is a power of two of a valid precision parameter. If the state is not valid (it was not retrieved using getState()) the behavior will be undefined.

      Parameters:
      state - the state
      Returns:
      the new sketch
      Throws:
      NullPointerException - if the passed array is null
      IllegalArgumentException - if the passed array has invalid length

    • copy

      public HyperLogLog copy()
      Creates a copy of this sketch.
      Returns:
      the copy

    • downsize

      public HyperLogLog downsize(int p)
      Returns a downsized copy of this sketch with a precision that is not larger than the given precision parameter.
      Parameters:
      p - the precision parameter used for downsizing
      Returns:
      the downsized copy
      Throws:
      IllegalArgumentException - if the precision parameter is invalid

    • merge

      public static HyperLogLog merge(HyperLogLog sketch1, HyperLogLog sketch2)
      Merges two HyperLogLog sketches into a new sketch.

      The precision of the merged sketch is given by the smaller precision of both sketches.

      Parameters:
      sketch1 - the first sketch
      sketch2 - the second sketch
      Returns:
      the merged sketch
      Throws:
      NullPointerException - if one of both arguments is null

    • getState

      public byte[] getState()
      Returns a reference to the internal state of this sketch.

      The returned state is never null.

      Returns:
      the internal state of this sketch

    • getP

      public int getP()
      Returns the precision parameter of this sketch.
      Returns:
      the precision parameter

    • add

      public HyperLogLog add(long hashValue)
      Adds a new element represented by a 64-bit hash value to this sketch.

      In order to get good estimates, it is important that the hash value is calculated using a high-quality hash algorithm.

      Parameters:
      hashValue - a 64-bit hash value
      Returns:
      this sketch

    • addToken

      public HyperLogLog addToken(int token)
      Adds a new element represented by a 32-bit token obtained from computeToken(long).
      Parameters:
      token - a 32-bit hash token
      Returns:
      this sketch

    • computeToken

      public static int computeToken(long hashValue)
      Computes a token from a given 64-bit hash value.

      Instead of updating the sketch with the hash value using the add(long) method, it can alternatively be updated with the corresponding 32-bit token using the addToken(int) method.

      addToken(computeToken(hash)) is equivalent to add(hash)

      Tokens can be temporarily collected using for example an int[] array and added later using addToken(int) into the sketch resulting exactly in the same final state. This can be used to realize a sparse mode, where the sketch is created only when there are enough tokens to justify the memory allocation. It is sufficient to store only distinct tokens. Deduplication does not result in any loss of information with respect to distinct count estimation. Compare DistinctCountUtil.deduplicateTokens(int[], int, int).

      Parameters:
      hashValue - the 64-bit hash value
      Returns:
      the 32-bit token

    • add

      public HyperLogLog add(long hashValue, StateChangeObserver stateChangeObserver)
      Adds a new element represented by a 64-bit hash value to this sketch and passes, if the internal state has changed, decrements of the state change probability to the given StateChangeObserver.

      In order to get good estimates, it is important that the hash value is calculated using a high-quality hash algorithm.

      Parameters:
      hashValue - a 64-bit hash value
      stateChangeObserver - a state change observer
      Returns:
      this sketch

    • addToken

      public HyperLogLog addToken(int token, StateChangeObserver stateChangeObserver)
      Adds a new element, represented by a 32-bit token obtained from computeToken(long), to this sketch and passes, if the internal state has changed, decrements of the state change probability to the given StateChangeObserver.

      addToken(computeToken(hash), stateChangeObserver) is equivalent to add(hash, stateChangeObserver)

      Parameters:
      token - a 32-bit hash token
      stateChangeObserver - a state change observer
      Returns:
      this sketch

    • add

      public HyperLogLog add(HyperLogLog other)
      Adds another sketch.

      The precision parameter of the added sketch must not be smaller than the precision parameter of this sketch. Otherwise, an IllegalArgumentException will be thrown.

      Parameters:
      other - the other sketch
      Returns:
      this sketch
      Throws:
      NullPointerException - if the argument is null

    • getDistinctCountEstimate

      public double getDistinctCountEstimate()
      Returns an estimate of the number of distinct elements added to this sketch.
      Returns:
      estimated number of distinct elements

    • getDistinctCountEstimate

      public double getDistinctCountEstimate(HyperLogLog.Estimator estimator)
      Returns an estimate of the number of distinct elements added to this sketch using the given estimator.
      Parameters:
      estimator - the estimator
      Returns:
      estimated number of distinct elements

    • getStateChangeProbability

      public double getStateChangeProbability()
      Returns the probability of an internal state change when a new distinct element is added.
      Returns:
      the state change probability

    • isEmpty

      public boolean isEmpty()
      Returns true if the sketch is empty, corresponding to the initial state.
      Returns:
      true if the sketch is empty

    • reset

      public HyperLogLog reset()
      Resets this sketch to its initial state representing an empty set.
      Returns:
      this sketch