Module hash4j
Package com.dynatrace.hash4j.distinctcount

Class UltraLogLog

java.lang.Object
com.dynatrace.hash4j.distinctcount.UltraLogLog
public final class UltraLogLog extends Object
A sketch for approximate distinct counting that is more space efficient than HyperLogLog as described in Otmar Ertl, UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting, 2023

This implementation varies from the algorithm described in the paper by redefining nonzero register values by the mapping r -> r + 4*p - 8. Since the maximum register value in the paper is given by 4*w+3 = 263-4*p with w = 65-p, the maximum register value in this implementation is given by (263 - 4*p) + 4*p - 8 = 255 which is independent of p.

  • Field Details

    • MAXIMUM_LIKELIHOOD_ESTIMATOR

      public static final UltraLogLog.Estimator MAXIMUM_LIKELIHOOD_ESTIMATOR
      Bias-reduced maximum-likelihood estimator.

    • OPTIMAL_FGRA_ESTIMATOR

      public static final UltraLogLog.Estimator OPTIMAL_FGRA_ESTIMATOR
      Optimal further generalized remaining area (FGRA) estimator.

    • DEFAULT_ESTIMATOR

      public static final UltraLogLog.Estimator DEFAULT_ESTIMATOR
      The default estimator.

  • Method Details

    • create

      public static UltraLogLog create(int p)
      Creates an empty UltraLogLog 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

    • wrap

      public static UltraLogLog wrap(byte[] state)
      Returns a UltraLogLog 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 UltraLogLog copy()
      Creates a copy of this sketch.
      Returns:
      the copy

    • downsize

      public UltraLogLog 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 UltraLogLog merge(UltraLogLog sketch1, UltraLogLog sketch2)
      Merges two UltraLogLog 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 UltraLogLog 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 UltraLogLog 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 UltraLogLog 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 UltraLogLog 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 UltraLogLog add(UltraLogLog 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(UltraLogLog.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 UltraLogLog reset()
      Resets this sketch to its initial state representing an empty set.
      Returns:
      this sketch