假设对于一个二进制流，我们有一个针对长度为N的滑动窗口（window）的查询“最后的k个位中有多少个1？”(1<=k<=N)。

    对于该查询，若空间足够，可以通过空间复杂度O(N)，时间复杂度O(1)的简单的加减得到查询结果。所以这里要讨论的是对于N非常大的情况，即假设由于存储空间有限，我们不能存储整个窗口的数据。

    根据滑动窗口共有2^N种表示简单推算，任何能给出确切结果的算法都需要O(N)的空间，即该问题必须寻找近似算法。Datar-Gionis-Indyk-Motwani Algorithm（DGIM算法）是其中一种：该算法仅使用O(log²N)的空间，时间复杂度为O(logN)。     首先假设对于二进制流，其中每个位可以用一个时间戳（timestamp）标志该位进入流的时间（对于大小为N的滑动窗口，该时间戳可以用O(logN)位表示）。

     DGIM算法利用桶（bucket）对滑动窗口进行划分，每个桶保存以下信息：

• 桶的最右边位即最后进入流的位的时间戳；
• 桶的大小，即桶中1的个数，该数目位2的幂。

     对于以上信息，保存时间戳需要logN的空间，保存桶的大小需要loglogN的空间。

    使用桶对滑动窗口进行划分时遵循以下5条规则：

1. 桶最右边的位必须是1；
2. 1个位最多属于1个桶；
3. 每种大小的桶有1个或者两个（从1到最大的桶的大小）；
4. 每个桶的大小是2的幂；
5. 桶的大小从右到左非降序排列；

举例：

http://liulixiang.info/wp-content/uploads/2011/04/image_thumb.png

    DGIM算法中数据结构的更新：

1. 每一个新的位进入滑动窗口后，最左边一个位从窗口中移出（同时从桶中移出）；如果最左边的桶的时间戳是当前时间戳减去N（也就是说桶里已经没有处于窗口中的位），则放弃这个桶；
2. 对于新加入的位，如果其为0，则无操作；否则建立一个包含新加入位的大小为1的桶；
3. 由于新增一个大小为1的桶而出现3个桶大小为1，则合并最左边的两个桶为一个大小为2的桶；合并之后可能出现3个大小为2的桶，则合并最左边两个大小为2的桶得到一个大小为4的桶……依次类推直到到达最左边的桶。

举例（上图中最右边进入一个新的1后的结果）：

http://liulixiang.info/wp-content/uploads/2011/04/image_thumb1.png   

   可以给出DGIM的存储开销：桶的个数O(logN)，每个桶可以用O(logN)空间表示，保存表示一个窗口的所有桶所占的空间为O(log²N)。

    对于查询，首先寻找含最近k个位的拥有最大时间戳的桶b，查询结果为在k个为中所有桶的大小，加上b的大小的一半。一次查询的时间复杂度为O(logN)。

    该估计值误差（fractional error）的上下限为：

• 至少是正确值的50%：最差情况b中都是1，估计误差值是b的一半。
• 最多超过正确值的50%：最差情况b只有最右边一位为1。

    以上即为DGIM算法的全部内容，以下是对DGIM算法误差上下限的改进和算法应用范围的推广：

   误差改进：可以放宽同样大小的桶的个数的限制（不一定为1或2），设同时可以有r个同样大小的桶。此时误差为

                    http://liulixiang.info/wp-content/uploads/2011/04/clip_image001_thumb.png

    其中2^j为最大桶的大小，即得该误差的上界（upper bound）为1/(r-1)。

   DGIM算法应用的推广：可以对DGIM算法进行扩展，比如计算全部是非负数的窗口中数字的和（对于同时含有正数和负数的情况，DGIM无能为力）

   对于包含1到2m的非负数流，可以将每一位看做一个流（共m个），使用DGIM计算每个流中1的个数，则所求的和为：

                    http://liulixiang.info/wp-content/uploads/2011/04/clip_image0014_thumb.png

参考文献：

    M. Datar, A. Gionis, P. Indyk, and R. Motwani, “Maintaining stream statistics over sliding windows,” SIAM J. Computing 31, pp. 1794–1813, 2002.

    Anand Rajaraman and and Jeff Ullman, “Section 4.6: Counting Ones in a Window”,Mining of Massive Datasets, pp132-139, 2010