实践中的HyperLogLog

基数估计具有广泛的应用，对数据库系统尤其重要。过去提出了各种算法，其中HyperLogLog算法就是其中之一。本文提出了一系列改进，降低了该算法的内存需求，并显著提高了其在重要基数范围内的准确性。我们已经在Google的一个系统中实现了我们提出的算法，并进行了实证评估，与原始的HyperLogLog算法进行了比较。与HyperLogLog一样，我们改进的算法也能完美并行，并在单次遍历中计算基数估计。