超级日志

跳转至导航跳转至搜索HyperLogLog是一种用于计数差异问题的算法，它近似于多集合中不同元素的数量。 [1]计算多集的确切基数需要与基数成比例的内存量，这对于非常大的数据集而言是不切实际的。概率基数估计器（例如HyperLogLog算法）使用的内存明显少于此，以仅获得基数近似值为代价。 HyperLogLog算法能够估算的基数。 10 9的典型精度（标准误）为2％，使用1.5 kB内存。 [1] HyperLogLog是早期LogLog算法的扩展，[2]本身是从1984 Flajolet-Martin算法衍生而来的。 [3]

在Flajolet等人的原始论文中。 [1]以及在有关计数区别问题的相关文献中，术语“基数”用于表示具有重复元素的数据流中不同元素的数量。但是，在多集理论中，该术语是指多集的每个成员的重数之和。本文选择使用Flajolet的定义来与源保持一致。

HyperLogLog算法的基础是观察到，可以通过计算集合中每个数字的二进制表示形式中的前导零的最大数量，来估计均匀分布的随机数的多集的基数。如果观察到的前导零的最大数量为n，则该集合中不同元素的数量估计为2 n。 [1]

在HyperLogLog算法中，将哈希函数应用于原始多集中的每个元素，以获得基数与原始多集相同的均匀分布的随机数的多集。然后可以使用上面的算法来估计此随机分布集的基数。

使用上述算法获得的基数的简单估计具有方差大的缺点。在HyperLogLog算法中，通过将多集分成多个子集，计算这些子集中的每个子集中的数字中的前导零的最大数量，并使用调和平均值将每个子集的这些估计合并为整个集合的基数。 [4]

HyperLogLog具有三个主要操作：添加以向集合中添加新元素，计数以获取集合的基数，合并以获取两个集合的并集。可以使用包含-排除原理来计算某些派生运算，例如相交的基数或合并合并和计数运算的两个HyperLogLogs之间的差的基数。

HyperLogLog的数据存储在一个称为计数器的计数器数组M中，该计数器的大小为m，它们在初始状态下设置为0。

加法操作包括使用哈希函数h计算输入数据v的哈希，获取前b位（其中b是log 2⁡（m）{\ textstyle \ log _ {2}（m）}），以及给它们加1，以获得要修改的寄存器的地址。用剩余的位计算ρ（w）{\ textstyle \ rho（w）}，该函数返回最左边1的位置。寄存器的新值将是寄存器的当前值和ρ（w）{之间的最大值\ textstyle \ rho（w）}。

x：= h（v）j：= 1 + x 1 x 2。 。 。 x b 2 w：= x b + 1 x b + 2。 。 。 M [j]：= max（M [j]，ρ（w））{\ displaystyle {\ begin {aligned} x＆amp;：= h（v）\\ j＆amp;：= 1+ \ langle x_ {1} x_ {2} ... x_ {b} \ rangle _ {2} \\ w＆amp;：= x_ {b + 1} x_ {b + 2} ... \\ M [j]＆amp;：= \ max（ M [j]，\ rho（w））\\\ end {aligned}}}

计数算法包括计算m个寄存器的谐波平均值，并使用一个常数来得出计数的估计值E {\ textstyle E}：

Z =（∑ j = 1 m 2 − M [j]）− 1 {\ displaystyle Z = {\ Bigg（} \ sum _ {j = 1} ^ {m} {2 ^ {-M [j]}}} {\ Bigg）} ^ {-1}}

αm =（m∫0∞（log 2⁡（2 + u 1 + u））mdu）− 1 {\ displaystyle \ alpha _ {m} = \ left（m \ int _ {0} ^ {\ infty} \ left（\ log _ {2} \ left（{\ frac {2 + u} {1 + u}} \ right）\ right）^ {m} \，du \ right）^ {-1}}

直觉是n是M的未知基数，每个子集M j {\ textstyle M_ {j}}将具有n / m {\ textstyle n / m}个元素。那么max x∈M jρ（x）{\ textstyle \ max _ {x \ in M_ {j}} \ rho（x）}应该接近log 2⁡（n / m）{\ textstyle \ log _ { 2}（n / m）}。这些数量的2的谐波均值是m Z {\ textstyle mZ}，应该接近n / m {\ textstyle n / m}。因此，m 2 Z {\ textstyle m ^ {2} Z}应该近似为n。

最后，引入常数αm {\ textstyle \ alpha _ {m}}来纠正由于哈希冲突而在m 2 Z {\ textstyle m ^ {2} Z}中存在的系统性乘法偏差。

常数αm {\ textstyle \ alpha _ {m}}不容易计算，可以用公式[1]近似。

αm≈{m = 16 0.673 m = 32 0.697 m = 64 0.709 m≥128 0.7213 1 + 1.079 m {\ displaystyle \ alpha _ {m} \ approx {\ begin {cases} m = 16＆amp; 0.673 \\ m = 32＆amp; 0.697 \\ m = 64＆amp; 0.709 \\ m \ geq 128＆amp; {\ frac {0.7213} {1 + {\ frac {1.079} {m}}}} \ end {cases}}}

不过，HyperLogLog技术偏向于阈值低于5 2 m {\ textstyle {\ frac {5} {2}} m}的小基数。原始论文提出对小基数使用另一种算法，即线性计数。 [5]在以上提供的估计小于阈值E ＜的情况下。 5 2 m {\ textstyle E＆lt; {\ frac {5} {2}} m}，可以使用替代计算：

如果V = 0 {\ textstyle V = 0}，请使用上面的标准HyperLogLog估计器E {\ textstyle E}。

否则，请使用线性计数：E⋆= m log⁡（m V）{\ textstyle E ^ {\ star} = m \ log \ left（{\ frac {m} {V}} \ right）}

另外，对于非常大的基数接近寄存器大小的限制（对于32位寄存器，E> 2 32 30 {\ textstyle E＆{{frac {2 ^ {32}} {30}}}），基数可以通过以下方式估算：

E⋆= − 2 32 log⁡（1 − E 2 32）{\ displaystyle E ^ {\ star} =-2 ^ {32} \ log \ left（1-{\ frac {E} {2 ^ {32} }}\对）}

通过对上下限进行上述校正，可以将错误估计为σ= 1.04 / m {\ textstyle \ sigma = 1.04 / {\ sqrt {m}}}。

两个HLL（hll 1，hll 2 {\ textstyle hll_ {1}，hll_ {2}}）的合并操作包括获得每对寄存器j：1.的最大值。m {\ textstyle j：1 .. m}

h l l u n i o n [j] = max（h l l 1 [j]，h l l 2 [j]）{\ displaystyle hll_ {union} [j] = \ max（hll_ {1} [j]，hll_ {2} [j]）}

为了分析复杂度，使用了数据流（ϵ，δ）{\ displaystyle（\ epsilon，\ delta）}模型[6]，该模型分析了获得1±ϵ {\ displaystyle 1 \ pm \ epsilon }具有固定成功概率1-δ的近似值{\ displaystyle 1- \ delta}。 HLL的相对误差为1.04 / m {\ displaystyle 1.04 / {\ sqrt {m}}}}，它需要O（ϵ − 2 log⁡log⁡n + log⁡n）{\ displaystyle O（\ epsilon ^ {- 2} \ log \ log n + \ log n）}空间，其中n是设置的基数，m是寄存器的数量（通常小于一个字节大小）。

加法操作取决于哈希函数输出的大小。由于此大小是固定的，因此我们可以考虑添加操作的运行时间为O（1）{\ displaystyle O（1）}。

计数和合并操作取决于寄存器m的数量，其理论成本为O（m）{\ displaystyle O（m）}。在某些实现中（Redis）[7]，寄存器的数量是固定的，并且成本在文档中被认为是O（1）{\ displaystyle O（1）}。

HyperLogLog ++算法对HyperLogLog算法提出了一些改进，以减少内存需求并在某些基数范围内提高准确性：[6]

使用64位哈希函数，而不是原始论文中使用的32位。这减少了大基数的哈希冲突，从而可以删除大范围校正。

从线性计数转换为HLL计数时，对于小的基数会发现一些偏差。提出了经验偏差校正以减轻该问题。

提出了寄存器的稀疏表示以减少小基数的存储需求，如果基数增加，则可以稍后将其转换为密集表示。

当数据以单个流到达时，历史逆概率或mar估计器[8] [9]显着提高了HLL草图的准确性，并减少了36％的内存来实现给定的错误级别。对于单个流上的任何重复的不敏感的近似不同的计数草图，证明该估计器是最佳的。

单流场景也会导致HLL草图构造的变体.HLL-TailCut +使用的内存比原始HLL草图少45％，但以依赖于数据插入顺序且无法合并草图为代价。 [10]

^ a b c d e Flajolet，菲利普；埃西里（Eric）Fusy；奥利维尔·甘杜埃（Gandouet）； Meunier，Frédéric（2007）。 ＆＃34;超日志：一种近似最佳基数估计算法的分析＆＃34; （PDF）。离散数学和理论计算机科学论文集。法国南希。 AH：127–146。 CiteSeerX 10.1.1.76.4286。

^ Durand，M .； Flajolet，P.（2003年）。 ＆＃34; Log记录大基数的日志。 （PDF）。在G. Di Battista和U. Zwick（编辑）中。计算机科学讲义。年度欧洲算法研讨会（ESA03）。 2832。施普林格。第605–617页。

^ Flajolet，菲利普；马丁·G·奈杰尔（1985）。 ＆＃34;用于数据库应用程序的概率计数算法＆＃34; （PDF）。计算机与系统科学学报。 31（2）：182–209。 doi：10.1016 / 0022-0000（85）90041-8。

^ S Heule，M Nunkesser，大厅（2013）。 ＆＃34;实践中的HyperLogLog：最先进的基数估计算法的算法工程＆＃34; （PDF）。秒4. CS1维护：使用authors参数（链接）

^ Whang，Kyu-Young;范德赞丹（Vander-Zanden），布拉德（Brad T）；泰勒，霍华德M（1990）。 ＆＃34;用于数据库应用程序的线性时间概率计数算法。数据库系统上的ACM事务。 15（2）：208–229。 doi：10.1145 / 78922.78925。

^ Cohen，E.（2015年3月）。 ＆＃34;全程草图，再造：用于大量图形分析的HIP估计器。 IEEE知识和数据工程事务。 27（9）：2320–2334。 arXiv：1306.3284。 doi：10.1109 / TKDE.2015.2411606。

^ Ting，D.（2014年8月）。 ＆＃34;流式处理不同元素的近似计数：击败最佳批处理方法。第20届ACM SIGKDD国际知识发现和数据挖掘会议论文集（KDD＆＃39; 14）：442–451。 doi：10.1145 / 2623330.2623669。 ISBN 9781450329569。

^Q。周Y； Chen，S.（2017年5月）。 ＆＃34;位数更少：提高大型数据流基数估计的性能。 IEEE INFOCOM 2017-IEEE计算机通信会议：1–9。 doi：10.1109 / INFOCOM.2017.8057088。 ISBN 978-1-5090-5336-0。

＆＃34;用于Web分析和数据挖掘的概率数据结构|高度可扩展的Blog＆＃34;。 highscalable.wordpress.com。 2012年5月。