HyperLogLog.h File Reference

Functions used to work with HyperLogLog records. More...

#include "Descriptors/CountDistinctDescriptor.h"
#include <cmath>

Include dependency graph for HyperLogLog.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
double	get_alpha (const size_t m)
double	get_beta (const uint32_t zeros)
template<typename T >
double	get_harmonic_mean_denominator (T *M, uint32_t m)
template<typename T >
double	get_beta_adjusted_estimate (const size_t m, const uint32_t z, T *M)
template<typename T >
double	get_alpha_adjusted_estimate (const size_t m, T *M)
template<typename T >
uint32_t	count_zeros (T *M, size_t m)
template<class T >
size_t	hll_size (const T *M, const size_t bitmap_sz_bits)
template<class T1 , class T2 >
void	hll_unify (T1 *lhs, T2 *rhs, const size_t m)
int	hll_size_for_rate (const int err_percent)

Variables
int	g_hll_precision_bits

Detailed Description

Functions used to work with HyperLogLog records.

Author

Alex Suhan alex@.nosp@m.mapd.nosp@m..com Copyright (c) 2017 MapD Technologies, Inc. All rights reserved.

Definition in file HyperLogLog.h.

Function Documentation

template<typename T >

uint32_t count_zeros ( T *  M, size_t  m  )

inline

Definition at line 79 of file HyperLogLog.h.

Referenced by hll_size().

                                            {
  uint32_t zeros = 0;
  for (uint32_t i = 0; i < m; i++) {
    if (M[i] == 0) {
      zeros++;
    }
  }
  return zeros;
}

Here is the caller graph for this function:

double get_alpha ( const size_t  m )

inline

Definition at line 32 of file HyperLogLog.h.

Referenced by get_alpha_adjusted_estimate(), and get_beta_adjusted_estimate().

                                        {
  switch (m) {
    case 16:
      return 0.673;
    case 32:
      return 0.697;
    case 64:
      return 0.709;
    default:
      break;
  }
  double alpha = 0.7213 / (1 + 1.079 / m);
  return alpha;
}

Here is the caller graph for this function:

template<typename T >

double get_alpha_adjusted_estimate ( const size_t  m, T *  M  )

inline

Definition at line 74 of file HyperLogLog.h.

References get_alpha(), and get_harmonic_mean_denominator().

Referenced by hll_size().

                                                                {
  return (get_alpha(m) * m * m) * (1 / get_harmonic_mean_denominator(M, m));
};

Here is the call graph for this function:

Here is the caller graph for this function:

double get_beta ( const uint32_t  zeros )

inline

Definition at line 47 of file HyperLogLog.h.

Referenced by get_beta_adjusted_estimate().

                                             {
  // Using polynomial regression terms found in LogLog-Beta paper and Redis
  double zl = log(zeros + 1);
  double beta = -0.370393911 * zeros + 0.070471823 * zl + 0.17393686 * pow(zl, 2) +
                0.16339839 * pow(zl, 3) + -0.09237745 * pow(zl, 4) +
                0.03738027 * pow(zl, 5) + -0.005384159 * pow(zl, 6) +
                0.00042419 * pow(zl, 7);
  return beta;
}

Here is the caller graph for this function:

template<typename T >

double get_beta_adjusted_estimate ( const size_t  m, const uint32_t  z, T *  M  )

inline

Definition at line 68 of file HyperLogLog.h.

References get_alpha(), get_beta(), and get_harmonic_mean_denominator().

Referenced by hll_size().

                                                                                 {
  return (get_alpha(m) * m * (m - z) *
          (1 / (get_beta(z) + get_harmonic_mean_denominator(M, m))));
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

double get_harmonic_mean_denominator ( T *  M, uint32_t  m  )

inline

Definition at line 58 of file HyperLogLog.h.

Referenced by get_alpha_adjusted_estimate(), and get_beta_adjusted_estimate().

                                                              {
  double accumulator = 0.0;

  for (unsigned i = 0; i < m; i++) {
    accumulator += (1.0 / (1ULL << M[i]));
  }
  return accumulator;
}

Here is the caller graph for this function:

template<class T >

size_t hll_size ( const T *  M, const size_t  bitmap_sz_bits  )

inline

Definition at line 90 of file HyperLogLog.h.

References count_zeros(), get_alpha_adjusted_estimate(), and get_beta_adjusted_estimate().

Referenced by RangeJoinHashTable::approximateTupleCount(), OverlapsJoinHashTable::approximateTupleCount(), BaselineJoinHashTable::approximateTupleCount(), and count_distinct_set_size().

                                                                {
  size_t m = 1 << bitmap_sz_bits;

  uint32_t zeros = count_zeros(M, m);
  double estimate = get_alpha_adjusted_estimate(m, M);
  if (estimate <= 2.5 * m) {
    if (zeros != 0) {
      estimate = m * log(static_cast<double>(m) / zeros);
    }
  } else {
    if (bitmap_sz_bits == 14) {  // Apply LogLog-Beta adjustment only when p=14
      estimate = get_beta_adjusted_estimate(m, zeros, M);
    }
  }
  // No correction for large estimates since we're using 64-bit hashes.
  return estimate;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int hll_size_for_rate ( const int  err_percent )

inline

Definition at line 115 of file HyperLogLog.h.

References g_hll_precision_bits.

Referenced by anonymous_namespace{RelAlgExecutor.cpp}::decide_approx_count_distinct_implementation(), and anonymous_namespace{GroupByAndAggregate.cpp}::init_count_distinct_descriptors().

                                                    {
  double err_rate{static_cast<double>(err_percent) / 100.0};
  double k = ceil(2 * log2(1.04 / err_rate));
  // On the next line, 4 is the minimum for which we have an alpha adjustment factor in
  // get_alpha()
  return std::min(16, std::max(static_cast<int>(k), 4));
}

Here is the caller graph for this function:

template<class T1 , class T2 >

void hll_unify ( T1 *  lhs, T2 *  rhs, const size_t  m  )

inline

Definition at line 109 of file HyperLogLog.h.

Referenced by RangeJoinHashTable::approximateTupleCount(), OverlapsJoinHashTable::approximateTupleCount(), BaselineJoinHashTable::approximateTupleCount(), and count_distinct_set_union().

                                                        {
  for (size_t r = 0; r < m; ++r) {
    rhs[r] = lhs[r] = std::max(static_cast<int8_t>(lhs[r]), static_cast<int8_t>(rhs[r]));
  }
}

Here is the caller graph for this function:

Variable Documentation

int g_hll_precision_bits

Definition at line 54 of file GroupByAndAggregate.cpp.

Referenced by anonymous_namespace{RelAlgExecutor.cpp}::decide_approx_count_distinct_implementation(), CommandLineOptions::fillOptions(), hll_size_for_rate(), and anonymous_namespace{GroupByAndAggregate.cpp}::init_count_distinct_descriptors().