流中独立元素的数目统计
有这样一个问题，假定流元素选自某个全集，我们想知道某个时间段内，出现过的不同的元素数目。
一种明显的解决方法是在内存中保存当前已有的所有流元素列表，用哈希表或者搜索树来保存，以支持快速增加新元素，并检查元素是否存在。但是如果不同的元素数目太多，或者需要立即处理多个流，那么我们就无法在内存中存储所需数据。
这里介绍一种对独立元素个数进行估计的FM算法，FM算法通过将全集中的元素哈希到一个足够长的位串，就可以对独立元素个数进行估计。在讲FM算法之前，我们需要明确，哈希函数的一个重要性质是，相同元素上的哈希，结果也相同。
FM算法的基本思想是，如果流中看到的不同元素越多，那么我们看到的不同哈希值也会越多，在看到不同哈希值越多的同时，也越可能看到其中有一个值变得『异常』，比如，某个哈希值后面会以多个0结束。
任何时候在流元素上应用哈希函数时，哈希值的尾部将以一些0结束，当然也可能没有0，尾部0的数目称为尾长。假设流中目前所有已有哈希值的最大尾长为R，那么我们将使用2^R来估计到目前为止流中所看到的独立元素数目。
可以证明，如果独立元素数目远大于2^R，那发现一个尾长至少为R的概率接近1；如果独立元素数目远小于2^R，那发现一个尾长至少为R的概率接近0；
为了取得更精确的值，我们可以使用多个哈希函数，然后取2^R的平均值或者中位数。目前最好的方法是组合起来，首先将哈希函数分成小组，每个组内取平均值，然后在所有平均值中取中位数。
因为我们只需要记录每个哈希函数对应的最大尾长，所以对空间的占用非常小。
矩估计
首先定义矩，假定一个流由选自某个全集上的元素构成，并假定该全集中的所有元素都排好序，这样我们可以通过整数i来标记该序列中的第i个元素，假设该元素出现次数为mi，那流的k阶矩就是Σ(mi)^k。
也即，0阶矩是流中所有独立元素个数，1阶矩是所有元素出现次数mi之和，2阶矩是mi的平方和，用来度量流中元素分布的非均匀性，因此有时也被称为奇异数。出现次数越均匀，奇异数越小，越不均匀，2阶矩越大。
有一种AMS算法可以用来估计二阶矩，并且所使用的空间越多，估计结果也越精确。AMS的基本做法是在流中随机选择若干个位置，分别记录下这些位置对应的元素，将其出现次数置1，然后从当前位置往后读取到流尾，统计其出现次数。对于每个元素，都计算一个二阶矩的估计值，若假定n为流长，估计值为n*(2*出现次数-1)，然后对所有元素的估计值取平均。
这样做的理论基础是，任意变量的估计值都等于流的二阶矩。我们需要注意的是，最好在任何时候都尽可能保有足够多的变量，并在流增长时丢弃某些变量，丢弃的变量会被新变量取代，但必须保证选择任意位置的概率都相同。
窗口内的计数问题
假定我们要回答这样一个问题，有一个窗口大小为N的二进制流，我们希望在任何时候都能回答『对于任意的k<=N，最近k位中有多少个1』，可以证明，如果我们想得到对于任意的k<=N，最近k位中有多少个1的精确数目，任何长度小于N位的表示方法都无法得到精确结果。
接下来介绍DGIM算法，它能够使用O(log2N)位来表示大小为N的窗口，同时能保证窗口内1的数目的估计错误率不高于50%。而且其改进算法可以能在不显著增加占用空间的前提下，将错误率降低到任意大于零的分数之内，尽管当这个分数不断下降，空间复杂度会乘以某个不断增大的常数因子。
这里先给出一个DGIM算法的划分图：
我们将整个窗口划分成多个桶（与哈希中的桶不同），每个桶包含最右部也即最近的时间戳，桶中1的数目必须是2的幂，这也是该桶的大小。
而且，桶的最右部总是为1；每个1的位置都在某个桶中；一个位置只能属于1个桶；桶的大小从最小一直变化到某个最大值，相同大小的桶只可能有1到2个；所有桶的大小都必须是2的幂；从右到左扫描，桶的大小不会减小。
那怎么利用DGIM来回答上述问题呢，如果我们需要回答『窗口中最近k位中有多少个1』，那么DGIM算法会寻找某个具有最早时间戳的桶b，它至少包含k个最近位中的一部分。最后的估计值为桶b右部所有桶的大小之和加上桶b的一半大小。
