Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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

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

Definition at line 43 of file hyperloglog.cpp.

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

Definition at line 47 of file hyperloglog.cpp.

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

Definition at line 51 of file hyperloglog.cpp.

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

Definition at line 55 of file hyperloglog.cpp.

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

Definition at line 1482 of file hyperloglog.cpp.

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

template std::pair<size_t, uint8_t> thrill::core::hyperloglog::decodeHash< 25, 12 > ( HyperLogLogSparseRegister  )
template std::pair<size_t, uint8_t> thrill::core::hyperloglog::decodeHash< 25, 16 > ( HyperLogLogSparseRegister  )
template std::pair<size_t, uint8_t> thrill::core::hyperloglog::decodeHash< 25, 4 > ( HyperLogLogSparseRegister  )
std::vector< uint32_t > decodeSparseList ( const std::vector< uint8_t > &  sparseList)

Definition at line 1664 of file hyperloglog.cpp.

uint32_t encodeHash ( uint64_t  hash)

Definition at line 1527 of file hyperloglog.cpp.

References tlx::clz().

template uint32_t thrill::core::hyperloglog::encodeHash< 25, 12 > ( uint64_t  )
template uint32_t thrill::core::hyperloglog::encodeHash< 25, 16 > ( uint64_t  )
template uint32_t thrill::core::hyperloglog::encodeHash< 25, 4 > ( uint64_t  )
uint32_t thrill::core::hyperloglog::encodePair ( uint32_t  index,
uint8_t  value 
)

Definition at line 1512 of file hyperloglog.cpp.

References lowerNBitMask().

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

Perform a varint and a difference encoding.

Definition at line 1646 of file hyperloglog.cpp.

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

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

Definition at line 598 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 691 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 783 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 879 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 977 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 1073 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 1172 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 1274 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 1376 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 122 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 166 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 242 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 332 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 417 of file hyperloglog.cpp.

References estimateBiasCalculation().

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

Definition at line 504 of file hyperloglog.cpp.

References estimateBiasCalculation().

static double thrill::core::hyperloglog::estimateBiasCalculation ( double  rawEstimate,
const double *  estimatedData,
const double *  biasData,
size_t  estimateSize 
)
inlinestatic
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().

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

Definition at line 1473 of file hyperloglog.cpp.

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

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

Definition at line 1631 of file hyperloglog.cpp.

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

Definition at line 1557 of file hyperloglog.cpp.

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.

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

Definition at line 36 of file hyperloglog.cpp.

References s_thresholds.

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

Definition at line 1477 of file hyperloglog.cpp.

Referenced by decodeHash().

Variable Documentation

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.

Referenced by threshold().