没有合适的资源?快使用搜索试试~ 我知道了~
首页提升HyperLogLog估计精度:新算法消除大小卡方偏差
"这篇论文《New Cardinality Estimation Algorithms for HyperLogLog Sketches》由Otmar Ertl撰写,发表于2017年2月27日。主要探讨了针对HyperLogLog(HLL)哈希桶进行新估计算法的研究。HLL是一种常用于大数据集估计独特元素数量的数据结构,特别适用于高维空间中的数据压缩和估计。 首先,作者提出了一种理论驱动的扩展,针对原算法在处理小和大数据集时存在的偏差问题,设计了一个新的估计方法。这个改进旨在消除原有HLL估算在极端情况下可能出现的不准确性,使得估计结果更加准确,尤其对于数据规模较小或较大的情况。 论文的核心贡献是基于最大似然原理,发展出第二个无偏估计方法。这种方法不仅理论上具有无偏性,而且与之配套的是一个强大且高效的数值计算算法,能够有效地计算估计值。最大似然估计法的引入,使得处理单一HLL桶的数据估计更为精确,同时也适用于多个HLL桶的情况,如并集、交集或相对补集的元素计数,相较于传统的包含-排除原则,它能提供更准确的结果。 作者通过广泛的模拟实验来验证这些新算法的有效性和性能,这包括对不同数据流和大型数据集的测试,确保了在实际应用中能够提供稳定且精确的元素计数估计。这项工作为大数据处理中的元素唯一性计数提供了一种更为可靠和精确的方法,对于优化大数据分析的效率和精度具有重要意义。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/16821193/bga.jpg)
Figure 2: The distribution of the relative estimation error for the linear counting esti-
mator after evaluation of 10 000 randomly generated bitmaps of size 2
12
which
correspond to HyperLogLog sketches with parameters p = 12 and q = 0.
Figure 3: The distribution of the relative estimation error over the cardinality for the
original estimation algorithm after evaluation of 10 000 randomly generated
HyperLogLog data structures with parameters p = 12 and q = 20.
10
![](https://csdnimg.cn/release/download_crawler_static/16821193/bgb.jpg)
of underestimating the cardinalities, they are now overestimated. Another indication for
the incorrectness of the proposed large range correction is the fact that it is not even
defined for all possible states. For instance, consider a (p, q)-HyperLogLog sketch with
p+q = 32 for which all registers are equal to the maximum possible value q +1. The raw
estimate would be ˆn
raw
= α
m
2
33
, which is greater than 2
32
and outside of the domain
of the large range correction formula.
A simple approach to avoid the need of any large range correction is to extend the
operating range of the raw estimator to larger cardinalities. This can be easily accom-
plished by increasing p + q, which corresponds to using hash values with more bits.
Each additional bit doubles the operating range which scales like 2
p+q
. However, in case
q ≥ 31 the number of possible register values, which are {0, 1, . . . , q + 1}, is greater than
32 which is no longer representable by 5-bit registers. Therefore, it was proposed to use
6 bits per register in combination with 64-bit hash values [7]. Even larger hash values
are needless in practice, because it is unrealistic to encounter cardinalities of order 2
64
.
3.1. Derivation of the raw estimator
In order to better understand why the raw estimator fails for small and large cardinalities,
we start with a brief and simple derivation without the restriction to large cardinalities
(n → ∞) and without using complex analysis as in [6].
Let us assume that the register values have following cumulative distribution function
P (K ≤ k|λ) = e
−
λ
m2
k
. (16)
For now we ignore that this distribution has infinite support and differs from the register
value distribution under the Poisson model (6), whose support is limited to the range
[0, q + 1]. For a random variable K obeying (16) the expectation of 2
−K
is given by
E(2
−K
) =
∞
X
k=−∞
2
−k
e
−
λ
m2
k
− e
−
λ
m2
k−1
=
1
2
∞
X
k=−∞
2
k
e
−
λ
m
2
k
=
α
∞
m ξ(log
2
(λ/m))
λ
, (17)
where the function
ξ(x) := log(2)
∞
X
k=−∞
2
k+x
e
−2
k+x
(18)
is a smooth periodic function with period 1. Numerical evaluations indicate that this
function can be bounded by 1 −ε
ξ
≤ ξ(x) ≤ 1 + ε
ξ
with ε
ξ
:= 9.885 × 10
−6
(see Fig. 4).
This value can also be found using Fourier analysis as shown in Appendix A.
Let K
1
, . . . , K
m
be a sample distributed according to (16). For large sample sizes
m → ∞ we have asymptotically
E
1
2
−K
1
+ . . . + 2
−K
m
=
m→∞
1
E(2
−K
1
+ . . . + 2
−K
m
)
=
1
mE(2
−K
)
. (19)
11
![](https://csdnimg.cn/release/download_crawler_static/16821193/bgc.jpg)
Figure 4: The deviation of ξ(x) from 1.
Together with (17) we obtain
λ = E
α
∞
m
2
ξ(log
2
(λ/m))
2
−K
1
+ . . . + 2
−K
m
for m → ∞. (20)
Therefore, the asymptotic relative bias of
ˆ
λ =
α
∞
m
2
2
−K
1
+ . . . + 2
−K
m
(21)
is bounded by ε
ξ
, which makes this statistic a good estimator for the Poisson parameter.
It also corresponds to the raw estimator (11), if the Poisson parameter estimate is used
as cardinality estimate (see Section 2.4).
3.2. Limitations of the raw estimator
The raw estimator is based on two prerequisites. First, the number of registers needs
to be sufficiently large (m → ∞). And second, the distribution of register values can
be described by (16). However, the latter is not true for small and large cardinalities,
which is finally the reason for the bias of the raw estimator.
A random variable K
0
with cumulative distribution function (16) can be transformed
into a random variable K with cumulative distribution function (6) using
K = min
max
K
0
, 0
, q + 1
. (22)
Therefore, register values K
1
, . . . , K
m
can be seen as the result after applying this trans-
formation to a sample K
0
1
, . . . , K
0
m
of the distribution described by (16). If all registers
values fall into the range [1, q], they must be identical to the values K
0
1
, . . . , K
0
m
. In
other words, the observed register values are also a plausible sample of the assumed
distribution described by (16) in this case. Hence, as long as all or at least most register
values are in the range [1, q], which is the case if 2
p
λ 2
p+q
, the approximation of
12
剩余55页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
weixin_38714910
- 粉丝: 4
- 资源: 921
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 贵州煤矿矿井水分类与处理策略:悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比:ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台:农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型:实证与应用
- 井下智能变电站:Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案:基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能:拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学:设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究:理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统:节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)