DGIM算法的空间复杂度是O((log2N)^2)
我们还要考虑DGIM的条件保持问题，每当一个一个新的位到达时，如果导致最早的桶超出了窗口，那将该桶丢弃；如果新来的位是0，那现有的桶（不包括因为超出窗口而丢弃的桶）不需要做任何改变，而如果新来的位是1，那么基于当前时间戳建立一个新的大小为1的桶，如果这导致了大小为1的桶的个数变成了3个，那就将更早的两个大小为1桶合并为一个大小为2的桶，如果这又导致大小为2的桶的个数超限，那就继续合并。
为了降低错误率，我们可以修改允许具有相同大小的桶的数目，前面是1或2，可以修改为r和r-1，这样所得到的错误率为：
如果r足够大，上述错误率可以小于任意想要的值。
衰减窗口
衰减窗口是我个人认为这一章最实用的技术，它可以用来寻找近期的最常见元素。
我们考虑一下最常见元素问题，假定我们要挖掘出当前最流行的电影，我们希望哈利波特这样虽然售出很多票，但时间过早的电影流行度较低。另一方面，一部近10周每周都售出n张票的电影会比仅上周售出2n张票但是再往前一张都票都没售出的电影的流行度要高。
我们可以把每部电影想象成一个位流，如果第i张票属于这部电影，则第i位置1，否则置0，这样我们就可以利用前面的DGIM算法去计算，一个时间段内，每部电影都卖了多少张票，然后以此来计算电影的流行程度。
当然我们可以有一种更好的方法，对问题进行重定义，不再查询窗口中1的数目，更精确的说，我们对流中已见的所有1计算一个平滑的累积值，其中采用的权重不断衰减。因此，元素在流中出现的越早，其权重也就越小。这就是我们要介绍的指数衰减窗口，其定义式如下：
我们定义c是一个很小的常数（比如10^-9），式子中的i代表位置。
为了便于理解，这里再给出一张图：
这条曲线，就是权重的衰减曲线。
我们同样的将每部电影想象成一个位流，如果第i张票属于这部电影，则第i位置1，否则置0，这里的区别在于，我们不是直接对所有的1求和，而是通过衰减求和来计算电影的流行度。前面的那个式子里，如果第i张电影票属于该电影，那a就会为1，在于权重相乘，累加起来。不同的电影不同的位流，也会计算出不同的流行度。
另外，10^-9相当于给了一个大概能容纳最近10亿次购票记录的滑动窗口。
当新的元素到达时，对每一个位流需要做的很简单，先将当前的结果乘以(1-c)，因为相当于原先的所有元素都远了一个位置，所有的权重也就多乘一个(1-c)，然后对于新元素对应的那个电影位流的计算结果，加上1，因为根据上面的公式，第0个位置对应的权重正好是1。其实在上面那个公式里面，a负责判断对应位置的权重该不该被累加，(1-c)^i就是相应位置的权重。
还有，如果流中可能的电影数目非常巨大的话，我们可以设置一个阈值，比如1/2。如果某部电影的热门程度小于该值，其得分将被丢弃。其实，设置了阈值以后，任意时间保留得分的电影的数目是有限的。
频繁项集
其实在《浅谈机器学习基础》中就讲过Apriori这种求得频繁项集的方法，以及如何利用频繁项集求得关联规则。另外还讲过FP-growth，能比Apriori更快的发现频繁项集，且只需扫描数据集两次。
另外，用于发现频繁项集的数据以购物篮模型的形式存在。
Apriori算法这里就不重复讲了（可以去看文集中对应的文章），这里专门提一下更大数据集在内存中的处理。我们知道Apriori算法在对候选项C2进行计数的时候，是需要内存最大的步骤（也即对所有满足支持度阈值的C1频繁项进行组合）。我们希望能够降低这一步的内存占用，以避免产生内存抖动（在磁盘和内存之间反复传输数据）。
这里介绍PCY算法，它主要利用了Apriori第一遍扫描中可能有大量未用内存空间这一观察结果。
