IT·行·思·录

假设对于一个二进制流，我们有一个针对长度为N的滑动窗口（window）的查询“最后的k个位中有多少个1？”(1<=k<=N)。     对于该查询，若空间足够，可以通过空间复杂度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的个数，则所求的和为：                     [...]

Yahoo流计算系统S4的一点介绍。         目前最流行的大规模数据处理是MapReduce，不过MapReduce只是一个面向批处理的框架。其它情况则是流处理系统或针对特定问题的特殊解决方案（比如Pregel、GraphLab等等），当然还有“应用最广”的并行数据库。       流计算来自于一个信念：数据的价值随着时间的流逝而降低，所以事件出现后必须尽快地对它们进行处理，最好数据出现时便立刻对其进行处理，发生一个事件进行一次处理，而不是缓存起来成一批处理。       S4(Simple Scalable Streaming System)是Yahoo最新发布的一个开源流计算平台，引用项目开源地址(http://s4.io/)首页对S4的介绍：     S4 is a general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows programmers to easily develop applications for processing continuous unbounded streams of data.       即S4是一个通用的、可扩展性良好、具有部分容错能力、支持插件的分布式流计算平台，在该平台上程序员可以很方便地开发处理流数据的应用。       S4发布之后自然是立刻得到了大家的广泛关注（相对比较落后的我都在半个月前就看过本篇论文了，无奈在集中精力准备学位课考试），以下是我的论文阅读笔记 ：   ==== （这是liulixiang.info上有意义的分割线）====   S4: Distributed Stream Computing Platform   by Leonardo Neumeyer, Bruce [...]