概率论W10:DataStreams
当取样足够好的时候,当Datastream无限时,取样相当于一个物理规律.
Tail Inequalities;
一个经典的取样方法:Reservoir Sampling[水库抽样]
Add each element to S with probability M/n;
Concise sampling
以1/T的概率加入到取样之中.
如果我们用<value, count>来表示取样的样本,用concise sampling取样,对于什么样的<value, count>能做准确的估计,对于什么样的样本作出的估计是不准确的?
Effective for answering hot list queries;
所以,对k most frequent values的情况下的估计比较好;k most frequent 会在sampling中沉淀下来;