Thrill  0.1
Functions | Variables
thrill::core::hyperloglog Namespace Reference

Functions

template<size_t p>
constexpr double alpha ()
 
template<>
constexpr double alpha< 4 > ()
 
template<>
constexpr double alpha< 5 > ()
 
template<>
constexpr double alpha< 6 > ()
 
template<size_t sparsePrecision, size_t densePrecision>
std::pair< size_t, uint8_t > decodeHash (HyperLogLogSparseRegister reg)
 
template std::pair< size_t, uint8_t > decodeHash< 25, 12 > (HyperLogLogSparseRegister)
 
template std::pair< size_t, uint8_t > decodeHash< 25, 16 > (HyperLogLogSparseRegister)
 
template std::pair< size_t, uint8_t > decodeHash< 25, 4 > (HyperLogLogSparseRegister)
 
std::vector< uint32_t > decodeSparseList (const std::vector< uint8_t > &sparseList)
 
template<size_t sparsePrecision, size_t densePrecision>
uint32_t encodeHash (uint64_t hash)
 
template uint32_t encodeHash< 25, 12 > (uint64_t)
 
template uint32_t encodeHash< 25, 16 > (uint64_t)
 
template uint32_t encodeHash< 25, 4 > (uint64_t)
 
template<size_t sparsePrecision, size_t densePrecision>
uint32_t encodePair (uint32_t index, uint8_t value)
 
std::vector< uint8_t > encodeSparseList (const std::vector< uint32_t > &sparseList)
 Perform a varint and a difference encoding. More...
 
template<size_t p>
double estimateBias (double rawEstimate)
 
template<>
double estimateBias< 10 > (double rawEstimate)
 
template<>
double estimateBias< 11 > (double rawEstimate)
 
template<>
double estimateBias< 12 > (double rawEstimate)
 
template<>
double estimateBias< 13 > (double rawEstimate)
 
template<>
double estimateBias< 14 > (double rawEstimate)
 
template<>
double estimateBias< 15 > (double rawEstimate)
 
template<>
double estimateBias< 16 > (double rawEstimate)
 
template<>
double estimateBias< 17 > (double rawEstimate)
 
template<>
double estimateBias< 18 > (double rawEstimate)
 
template<>
double estimateBias< 4 > (double rawEstimate)
 
template<>
double estimateBias< 5 > (double rawEstimate)
 
template<>
double estimateBias< 6 > (double rawEstimate)
 
template<>
double estimateBias< 7 > (double rawEstimate)
 
template<>
double estimateBias< 8 > (double rawEstimate)
 
template<>
double estimateBias< 9 > (double rawEstimate)
 
static double estimateBiasCalculation (double rawEstimate, const double *estimatedData, const double *biasData, size_t estimateSize)
 
static double knearestNeighbor (int k, int index, double estimate, const double *bias, const double *estimateData, size_t estimateDataLength)
 
constexpr uint64_t lowerNBitMask (uint64_t n)
 
template<typename ForwardIt >
SparseListIterator< ForwardIt > makeSparseListIterator (ForwardIt it)
 
template<size_t precision>
std::vector< HyperLogLogSparseRegister > mergeSameIndices (const std::vector< HyperLogLogSparseRegister > &sparseList)
 
template<size_t precision>
std::pair< uint32_t, uint8_t > splitSparseRegister (const HyperLogLogSparseRegister &reg)
 
template<size_t p>
static double threshold ()
 
constexpr uint32_t upperNBitMask (uint32_t n)
 

Variables

static const double s_thresholds [15]
 

Function Documentation

◆ alpha()

constexpr double thrill::core::hyperloglog::alpha ( )

Definition at line 43 of file hyperloglog.cpp.

◆ alpha< 4 >()

constexpr double thrill::core::hyperloglog::alpha< 4 > ( )

Definition at line 47 of file hyperloglog.cpp.

◆ alpha< 5 >()

constexpr double thrill::core::hyperloglog::alpha< 5 > ( )

Definition at line 51 of file hyperloglog.cpp.

◆ alpha< 6 >()

constexpr double thrill::core::hyperloglog::alpha< 6 > ( )

Definition at line 55 of file hyperloglog.cpp.

◆ decodeHash()

std::pair< size_t, uint8_t > decodeHash ( HyperLogLogSparseRegister  reg)

Definition at line 1482 of file hyperloglog.cpp.

References tlx::clz(), lowerNBitMask(), and upperNBitMask().

◆ decodeHash< 25, 12 >()

template std::pair<size_t, uint8_t> thrill::core::hyperloglog::decodeHash< 25, 12 > ( HyperLogLogSparseRegister  )

Referenced by encodeHash().

◆ decodeHash< 25, 16 >()

template std::pair<size_t, uint8_t> thrill::core::hyperloglog::decodeHash< 25, 16 > ( HyperLogLogSparseRegister  )

Referenced by encodeHash().

◆ decodeHash< 25, 4 >()

template std::pair<size_t, uint8_t> thrill::core::hyperloglog::decodeHash< 25, 4 > ( HyperLogLogSparseRegister  )

Referenced by encodeHash().

◆ decodeSparseList()

std::vector< uint32_t > decodeSparseList ( const std::vector< uint8_t > &  sparseList)

Definition at line 1662 of file hyperloglog.cpp.

◆ encodeHash()

uint32_t encodeHash ( uint64_t  hash)

Definition at line 1527 of file hyperloglog.cpp.

References tlx::clz(), decodeHash< 25, 12 >(), decodeHash< 25, 16 >(), decodeHash< 25, 4 >(), encodeHash< 25, 12 >(), encodeHash< 25, 16 >(), and encodeHash< 25, 4 >().

◆ encodeHash< 25, 12 >()

template uint32_t thrill::core::hyperloglog::encodeHash< 25, 12 > ( uint64_t  )

Referenced by encodeHash().

◆ encodeHash< 25, 16 >()

template uint32_t thrill::core::hyperloglog::encodeHash< 25, 16 > ( uint64_t  )

Referenced by encodeHash().

◆ encodeHash< 25, 4 >()

template uint32_t thrill::core::hyperloglog::encodeHash< 25, 4 > ( uint64_t  )

Referenced by encodeHash().

◆ encodePair()

uint32_t thrill::core::hyperloglog::encodePair ( uint32_t  index,
uint8_t  value 
)

Definition at line 1512 of file hyperloglog.cpp.

References lowerNBitMask().

◆ encodeSparseList()

std::vector< uint8_t > encodeSparseList ( const std::vector< uint32_t > &  sparseList)

Perform a varint and a difference encoding.

Definition at line 1644 of file hyperloglog.cpp.

Referenced by HyperLogLogRegisters< p >::mergeSparse().

◆ estimateBias()

double thrill::core::hyperloglog::estimateBias ( double  rawEstimate)

Referenced by estimateBiasCalculation().

◆ estimateBias< 10 >()

double thrill::core::hyperloglog::estimateBias< 10 > ( double  rawEstimate)

Definition at line 598 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 11 >()

double thrill::core::hyperloglog::estimateBias< 11 > ( double  rawEstimate)

Definition at line 691 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 12 >()

double thrill::core::hyperloglog::estimateBias< 12 > ( double  rawEstimate)

Definition at line 783 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 13 >()

double thrill::core::hyperloglog::estimateBias< 13 > ( double  rawEstimate)

Definition at line 879 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 14 >()

double thrill::core::hyperloglog::estimateBias< 14 > ( double  rawEstimate)

Definition at line 977 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 15 >()

double thrill::core::hyperloglog::estimateBias< 15 > ( double  rawEstimate)

Definition at line 1073 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 16 >()

double thrill::core::hyperloglog::estimateBias< 16 > ( double  rawEstimate)

Definition at line 1172 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 17 >()

double thrill::core::hyperloglog::estimateBias< 17 > ( double  rawEstimate)

Definition at line 1274 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 18 >()

double thrill::core::hyperloglog::estimateBias< 18 > ( double  rawEstimate)

Definition at line 1376 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 4 >()

double thrill::core::hyperloglog::estimateBias< 4 > ( double  rawEstimate)

Definition at line 122 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 5 >()

double thrill::core::hyperloglog::estimateBias< 5 > ( double  rawEstimate)

Definition at line 166 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 6 >()

double thrill::core::hyperloglog::estimateBias< 6 > ( double  rawEstimate)

Definition at line 242 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 7 >()

double thrill::core::hyperloglog::estimateBias< 7 > ( double  rawEstimate)

Definition at line 332 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 8 >()

double thrill::core::hyperloglog::estimateBias< 8 > ( double  rawEstimate)

Definition at line 417 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBias< 9 >()

double thrill::core::hyperloglog::estimateBias< 9 > ( double  rawEstimate)

Definition at line 504 of file hyperloglog.cpp.

References estimateBiasCalculation().

◆ estimateBiasCalculation()

static double thrill::core::hyperloglog::estimateBiasCalculation ( double  rawEstimate,
const double *  estimatedData,
const double *  biasData,
size_t  estimateSize 
)
inlinestatic

Definition at line 100 of file hyperloglog.cpp.

References estimateBias(), and knearestNeighbor().

Referenced by estimateBias< 10 >(), estimateBias< 11 >(), estimateBias< 12 >(), estimateBias< 13 >(), estimateBias< 14 >(), estimateBias< 15 >(), estimateBias< 16 >(), estimateBias< 17 >(), estimateBias< 18 >(), estimateBias< 4 >(), estimateBias< 5 >(), estimateBias< 6 >(), estimateBias< 7 >(), estimateBias< 8 >(), and estimateBias< 9 >().

◆ knearestNeighbor()

static double thrill::core::hyperloglog::knearestNeighbor ( int  k,
int  index,
double  estimate,
const double *  bias,
const double *  estimateData,
size_t  estimateDataLength 
)
inlinestatic

Definition at line 61 of file hyperloglog.cpp.

Referenced by estimateBiasCalculation().

◆ lowerNBitMask()

constexpr uint64_t thrill::core::hyperloglog::lowerNBitMask ( uint64_t  n)

Definition at line 1473 of file hyperloglog.cpp.

Referenced by decodeHash(), encodePair(), and splitSparseRegister().

◆ makeSparseListIterator()

SparseListIterator<ForwardIt> thrill::core::hyperloglog::makeSparseListIterator ( ForwardIt  it)

Definition at line 1629 of file hyperloglog.cpp.

◆ mergeSameIndices()

std::vector<HyperLogLogSparseRegister> thrill::core::hyperloglog::mergeSameIndices ( const std::vector< HyperLogLogSparseRegister > &  sparseList)

Definition at line 1557 of file hyperloglog.cpp.

References operator!=(), thrill::common::operator*(), operator++(), operator==(), and gen_data::value.

◆ splitSparseRegister()

std::pair<uint32_t, uint8_t> thrill::core::hyperloglog::splitSparseRegister ( const HyperLogLogSparseRegister &  reg)

Definition at line 1505 of file hyperloglog.cpp.

References lowerNBitMask(), and gen_data::value.

◆ threshold()

static double thrill::core::hyperloglog::threshold ( )
inlinestatic

Definition at line 36 of file hyperloglog.cpp.

Referenced by PS5Context< Parameters >::sequential_threshold().

◆ upperNBitMask()

constexpr uint32_t thrill::core::hyperloglog::upperNBitMask ( uint32_t  n)

Definition at line 1477 of file hyperloglog.cpp.

Referenced by decodeHash().

Variable Documentation

◆ s_thresholds

const double s_thresholds[15]
static
Initial value:
= {
10, 20, 40, 80, 220, 400, 900, 1800,
3100, 6500, 11500, 20000, 50000, 120000, 350000
}

Definition at line 30 of file hyperloglog.cpp.