哪位大神知道此女名字来讲一下DGIM算法

来源：蜘蛛抓取(WebSpider) 时间：2017-02-17 20:17 标签： dgim
DGIM算法：估计滑动窗口中的1的个数
对于该查询，若空间足够，可以通过空间复杂度O(N)，时间复杂度O(1)的简单的加减得到查询结果。所以这里要讨论的是对于N非常大的情况，即假设由于存储空间有限，我们不能存储整个窗口的数据。
根据滑动窗口共有2N种表示简单推算，任何能给出确切结果的算法都需要O(N)的空间，即该问题必须寻找近似算法。Datar-Gionis-Indyk-Motwani
Algorithm（DGIM算法）是其中一种：该算法仅使用O(log2N)的空间，时间复杂度为O(logN)。&&&&
首先假设对于二进制流，其中每个位可以用一个时间戳（timestamp）标志该位进入流的时间（对于大小为N的滑动窗口，该时间戳可以用O(logN)位表示）。
DGIM算法利用桶（bucket）对滑动窗口进行划分，每个桶保存以下信息：
桶的最右边位即最后进入流的位的时间戳；
桶的大小，即桶中1的个数，该数目位2的幂。
对于以上信息，保存时间戳需要logN的空间，保存桶的大小需要loglogN的空间。
使用桶对滑动窗口进行划分时遵循以下5条规则：
桶最右边的位必须是1；
1个位最多属于1个桶；
每种大小的桶有1个或者两个（从1到最大的桶的大小）；
每个桶的大小是2的幂；
桶的大小从右到左非降序排列；
DGIM算法中数据结构的更新：
每一个新的位进入滑动窗口后，最左边一个位从窗口中移出（同时从桶中移出）；如果最左边的桶的时间戳是当前时间戳减去N（也就是说桶里已经没有处于窗口中的位），则放弃这个桶；
对于新加入的位，如果其为0，则无操作；否则建立一个包含新加入位的大小为1的桶；
由于新增一个大小为1的桶而出现3个桶大小为1，则合并最左边的两个桶为一个大小为2的桶；合并之后可能出现3个大小为2的桶，则合并最左边两个大小为2的桶得到一个大小为4的桶……依次类推直到到达最左边的桶。
举例（上图中最右边进入一个新的1后的结果）：
&& 可以给出DGIM的存储开销：桶的个数O(logN)，每个桶可以用O(logN)空间表示，保存表示一个窗口的所有桶所占的空间为O(log2N)。
对于查询，首先寻找含最近k个位的拥有最大时间戳的桶b，查询结果为在k个为中所有桶的大小，加上b的大小的一半。一次查询的时间复杂度为O(logN)。
该估计值误差（fractional error）的上下限为：
至少是正确值的50%：最差情况b中都是1，估计误差值是b的一半。
最多超过正确值的50%：最差情况b只有最右边一位为1。
以上即为DGIM算法的全部内容，以下是对DGIM算法误差上下限的改进和算法应用范围的推广：
&&&误差改进：可以放宽同样大小的桶的个数的限制（不一定为1或2），设同时可以有r个同样大小的桶。此时误差为
&&&&&&&&&&&&&&&&&&&&
其中2j为最大桶的大小，即得该误差的上界（upper
bound）为1/(r-1)。
&& DGIM算法应用的推广：可以对DGIM算法进行扩展，比如计算全部是非负数的窗口中数字的和（对于同时含有正数和负数的情况，DGIM无能为力）
对于包含1到2m的非负数流，可以将每一位看做一个流（共m个），使用DGIM计算每个流中1的个数，则所求的和为：
&&&&&&&&&&&&&&&&&&&&
参考文献：
&&& M. Datar, A.
Gionis, P. Indyk, and R. Motwani, “Maintaining stream statistics
over sliding windows,” SIAM J. Computing 31, pp. ,
Rajaraman and and Jeff Ullman, “Section 4.6: Counting Ones in a
Window”,Mining of Massive Datasets, pp132-139, 2010
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

我要回帖

更多关于 dgim 的文章

 

随机推荐