文章归档

linear counting algorithm

最近看了篇文章:Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory

比较感兴趣,于是找了原论文来看看:A Linear-Time Probabilistic Counting Algorithm for Database Applications / HyperLogLog : the analysis of a near-optimal cardinality estimation algorithm. 无奈hyperloglog实在复杂,难以理解,哪天看懂了再分享吧。

linear counting的作用就是统计集合的容量。算法思想和bloom-filter差不多,很多时候精确计算是很难做到的,但是可以允许一定的误差,从而通过这个误差的概率分析来折射整个全局的概貌。

  1. Algorithm Basic Linear Counting:
  2.     Let  key_{i} = the key for the ith tuple in the relation.
  3.     Initialize the bit map to "0"s.
  4.     for i = 1 to q do
  5.         hash_value = hash( key_{i} )
  6.         bit map(hash_value) = "1"
  7.     end for
  8.     U_{n} = number of "0"s in the bit map
  9.     V_{n} = U_{n}/m
  10.     \hat{n} \approx -m ln{V_{n}}

论文中引用到一个urn problem来阐述算法的思想,我简化一下描述。比如说每天某台服务器都会产生大量的日志,这个日志记录了用户的登录行为。就是username + timestamp,timestamp我省略,就是知道谁登录了即可。但是某用户可能一天登录很多次,就会产生多条记录。好了现在问题出来,我要通过这 个日志文件,统计一下今天到底有多少实际用户登录了我们的系统。把那些重复的元素从集合中去掉,考虑集合的互异性,问题的本质其实就是 the set cardinality。按照上面提到的算法,我们可以计算下图中column集合中的容量是11.1,偏差很小。


为什么这个算法可行?为什么urn为0的概率能反映出集合的容量?

一、证明

urn的数量是m,集合的元素个数是n,容量是 \hat{n} ,经过n次hash之后,会产生m个独立的随机事件:

如果第j个urn为空,则称事件 A_{j} 对应的随机变量的值 l_{A_{j}} 为1,表示urn为空这个事件发生了。否则 l_{A_{j}} 的值为0,表示没有发生。

所以,任何一个urn为空的概率都是: P(A_{j}) = \left(1 - \frac{1}{m}\right)^n, j \in (1,m)

hash之后,urn为空的总个数 U_{n} 即是: U_{n} = \sum\limits_{j=1}^{m} l_{A_{j}}

U_{n} 的数学期望是:

E(U_{n}) = \sum\limits_{j=1}^{m} P(A_{j}) = m\left(1 - \frac{1}{m} \right)^n \approx me^{-n/m} = me^{-t}, as (n,m \to \infty)

在足够随机的情况下,我们通常认为期望 E(U_{n}) 就是实际的。所以知道urn为0的个数,知道urn的数量m,就能计算出 n 的近似值 \hat{n}

 

二、误差分析

利用方差公式来计算期望值的离散程度,前面我们知道了 E(U_{n}) ,现在计算 E(U_{n}^2)

因为任意两个urn都为空的概率是: P(A_{j}) \cap {P(A_{k})} = \left(1 - \frac{2}{m}\right)^n, j \neq k ,所以

E(U_{n}^2) = E\left((\sum\limits_{j=1}^{m} l_{A_{j}})^2\right) = E\left(\sum\limits_{j=1}^{m} l_{A_{j}}^2 \right) + 2E\left( \sum\limits_{j=1}^{m} \sum\limits_{i=1}^{j-1} l_{A_{i}}l_{A_{j}} \right)

= m\left(1 - \frac{1}{m}\right)^2 + 2\left(\frac{m(m - 1)}{2}\right)\left(1 - \frac{2}{m}\right)^n

所以, U_{n} 的方差是

Var(U_{n}) = E(U_{n}^2) - E(U_{n})^2

= m\left( \left( 1 - \frac{1}{m} \right)^n + (m - 1)\left( 1 - \frac{2}{m} \right)^2 - m\left( 1 - \frac{1}{m} \right)^{2n} \right)

= m\left( \left( 1 - \frac{1}{m} \right)^n - \left(1 - \frac{2}{m}\right)^n + m\left( \left(1 - \frac{2}{m} \right)^n - \left(1 - \frac{1}{m}\right)^{2n} \right)\right)

其实 (1 - \frac{2}{m} )^n \approx e^{-2t}(1 - \frac{1}{m})^{2n} \approx e^{-2t} 的值是非常逼近的了,不过作者为了精确误差的值,利用泰勒公式将这部分继续展开

\left( 1 - \frac{2}{m} \right)^n \approx exp\left[ n ln\left( 1 - \frac{2}{m} \right) \right]

\approx exp\left[ n\left( -\frac{2}{m} - \frac{1}{2}\left(\frac{4}{m^2}\right) - \frac{1}{3}\left( \frac{8}{m^3} \right) ... \right) \right]

= exp\left( - \frac{2n}{m} \right) * exp\left( - \frac{2n}{m^2} \right) * exp\left( - \frac{8}{3}\left( \frac{n}{m^3} \right)\right) ...

\left( 1 - \frac{1}{m} \right)^{2n} \approx exp\left[ 2n ln\left( 1 - \frac{1}{m} \right) \right]

\approx exp\left[ 2n\left( -\frac{1}{m}-\frac{1}{2}\left(\frac{1}{m^2}\right)-\frac{1}{3}\left(\frac{1}{m^3}\right) ... \right) \right]

= exp\left( -\frac{2n}{m} \right)*exp\left( -\frac{n}{m^2} \right)*exp\left( -\frac{2}{3}\left( \frac{n}{m^3} \right) \right) ...

所以  m\left( \left(1 - \frac{2}{m} \right)^n - \left(1 - \frac{1}{m}\right)^{2n} \right)

\approx m*exp\left( -\frac{2n}{m} \right)\left( exp\left( -\frac{2n}{m^2} \right) - exp\left( -\frac{n}{m^2} \right) \right)

\approx m * exp\left( -\frac{2n}{m} \right)\left(\left( 1 - \frac{2n}{m^2} \right) - \left( 1 - \frac{n}{m^2} \right)\right)

\approx m *\left( - \frac{n}{m^2} \right)*exp\left( -\frac{2n}{m} \right)

\approx -te^{-2t}, as(n,m \to \infty)

所以 Var(U_{n}) = E(U_{n}^2) - E(U_{n})^2 \approx m(e^{-t} - e^{-2t} - te^{-2t}) = me^{-t}(1-(1+t)e^{-t}), t = n/m ,t是n/m的比率,其实只要这个比率不太小,实际的结果已经非常接近理论值了。

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>