Module hash4j
Package com.dynatrace.hash4j.distinctcount

Class MartingaleEstimator

java.lang.Object
com.dynatrace.hash4j.distinctcount.MartingaleEstimator
All Implemented Interfaces:
StateChangeObserver
public final class MartingaleEstimator extends Object implements StateChangeObserver
A martingale estimator, that can be used in conjunction with a distinct counter such as HyperLogLog or UltraLogLog to obtain slightly more accurate estimates for non-distributed data streams than the corresponding standard estimators. For distributed data streams, which require merging of partial results into a final result, the use of this martingale estimator is not very useful and therefore not recommended.

In order to get correct estimates, this estimator must be updated with every single add operation of the corresponding distinct count data structure using HyperLogLog.add(long, StateChangeObserver) and UltraLogLog.add(long, StateChangeObserver), respectively.

The estimator will become invalid, if the associated data structure is modified using non-element addition operations such as HyperLogLog.add(HyperLogLog) or UltraLogLog.add(UltraLogLog). It is possible to initiate a new martingale estimator using the values returned by getStateChangeProbability() and getDistinctCountEstimate() of the corresponding distinct counter. At that point, the martingale estimator returns the same estimate as the standard estimator. However, if many further elements are added, the martingale estimator may again produce better estimates.

The estimator remains valid if the associated data structure is downsized with HyperLogLog.downsize(int) or UltraLogLog.downsize(int).

References:

  • Ting, Daniel. "Streamed approximate counting of distinct elements: Beating optimal batch methods." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.
  • Cohen, Edith. "All-distances sketches, revisited: HIP estimators for massive graphs analysis." Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 2014.
  • Pettie, Seth, Dingyu Wang, and Longhui Yin. "Non-mergeable sketching for cardinality estimation." arXiv preprint arXiv:2008.08739 (2020).

  • Constructor Summary

    Constructors
    Constructor
    Description
    MartingaleEstimator()
    Constructor.
    MartingaleEstimator(double distinctCountEstimate, double stateChangeProbability)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    getDistinctCountEstimate()
    Returns the distinct count estimate.
    void
    reset()
    Resets the martingale estimator to its initial state.
    void
    set(double distinctCountEstimate, double stateChangeProbability)
    Sets the martingale estimator to a given distinct count estimate and a given state change probability.
    void
    stateChanged(double probabilityDecrement)
    This method is called whenever the internal state of the approximate distinct counter has changed.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • MartingaleEstimator

      public MartingaleEstimator()
      Constructor.

    • MartingaleEstimator

      public MartingaleEstimator(double distinctCountEstimate, double stateChangeProbability)
      Constructor.

      Can be used to continue estimation if an estimate of the current distinct count is known and if the current state change probability of the accompanying sketch is known.

      Parameters:
      distinctCountEstimate - the current distinct count estimate
      stateChangeProbability - the current state change probability of the accompanying sketch

  • Method Details

    • reset

      public void reset()
      Resets the martingale estimator to its initial state.

    • set

      public void set(double distinctCountEstimate, double stateChangeProbability)
      Sets the martingale estimator to a given distinct count estimate and a given state change probability.

      Can be used to continue estimation if an estimate of the current distinct count is known and if the current state change probability of the accompanying sketch is known.

      Parameters:
      distinctCountEstimate - the current distinct count estimate
      stateChangeProbability - the current state change probability of the accompanying sketch

    • getDistinctCountEstimate

      public double getDistinctCountEstimate()
      Returns the distinct count estimate.
      Returns:
      the distinct count estimate

    • stateChanged

      public void stateChanged(double probabilityDecrement)
      Description copied from interface: StateChangeObserver
      This method is called whenever the internal state of the approximate distinct counter has changed. After a state change, the probability of a next state change is usually smaller. The positive decrement of this state change probability is passed as an argument.
      Specified by:
      stateChanged in interface StateChangeObserver
      Parameters:
      probabilityDecrement - the positive probability decrement

    • toString

      public String toString()
      Overrides:
      toString in class Object