摘要:使用原理设想成一次不断投硬币的过程,非正面即反面每一面的概率为。而当时,的概率接近为。所以,当时,没有一次投掷次数大于的概率几乎为。生成连续个的概率是,那么我们得到这个串时,可以估算,这个数据集的基数是。
序
对于海量数据来说,数据内存占用会变得很高. Probabilistic数据结构牺牲了一下准确率去换取更低内存占用。比如一个HyperLogLog的数据结构只需要花费12KB内存,就可以计算接近2^64个不同元素的基数,而错误率在1.625%.
场景HyperLogLog一个常用的场景就是统计网站的UV。
基数简单来说,基数(cardinality,也译作势),是指一个集合(这里的集合允许存在重复元素)中不同元素的个数。例如看下面的集合:
{1,2,3,4,5,2,3,9,7}
这个集合有9个元素,但是2和3各出现了两次,因此不重复的元素为1,2,3,4,5,9,7,所以这个集合的基数是7。
net.agkn hll 1.6.0
使用
@Test public void testSimpleUse(){ final int seed = 123456; HashFunction hash = Hashing.murmur3_128(seed); // data on which to calculate distinct count final Integer[] data = new Integer[]{1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 7, 7, 7, 8, 10}; final HLL hll = new HLL(13, 5); //number of bucket and bits per bucket for (int item : data) { final long value = hash.newHasher().putInt(item).hash().asLong(); hll.addRaw(value); } System.out.println("Distinct count="+ hll.cardinality()); }原理
设想成一次不断投硬币的过程,非正面即反面(每一面的概率为0.5)。 在这个过程中,投掷次数大于k的概率是0.5^k(连续投掷出k个反面),在一次过程中,投掷次数小于k的概率是(1-0.5)^k。
因此,在n次投掷过程中,投掷次数均小于k的概率是
P(x<=k)=(1-0.5^k)^n P(x>=k)=1-(1-0.5^k)^n
从以上公式,可以看出,当n<=k)的概率,接近为0。而当n>>k时,P(x<=k)的概率接近为0。所以,当n>>k时,没有一次投掷次数大于k的概率几乎为0。
将一次过程,理解成一个比特子串,反面为0,正面为1, 投掷次数k对应第一个1出现的位置,当统计子串足够多时,其最大的第一个1的位置为j,那么当n>>2^j时,P(x<=k)接近为0,当n<<2^j时,P(x>=0)也趋向为0。也就是说,在得到x=k的前提下,我们可以认为n=2^j。
再通俗点说明: 假设我们为一个数据集合生成一个8位的哈希串,那么我们得到00000111的概率是很低的,也就是说,我们生成大量连续的0的概率是很低的。生成连续5个0的概率是1/32,那么我们得到这个串时,可以估算,这个数据集的基数是32。
docHyperLogLog的核心思想原理
Probabilistic data Structures – Bloom filter and HyperLogLog for Big Data
HyperLogLog: 解读Cardinality Estimation算法(第一部分:基本概念)
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/67567.html
阅读 2150·2020-06-12 14:26
阅读 2456·2019-08-29 16:41
阅读 1842·2019-08-29 15:28
阅读 2430·2019-08-26 13:43
阅读 737·2019-08-26 13:37
阅读 2746·2019-08-23 18:13
阅读 2775·2019-08-23 15:31
阅读 993·2019-08-23 14:10