IT·行·思·录

2011年8月这一期的CACM上有一篇“An Overview of Business Intelligence Technology”，总结了商业智能(Business Intelligence, BI)的运行组成部分和相关关键技术，对于理解整个商业智能的架构很有帮助。 这篇文章特别说明了一些BI领域在“大数据（big data）”时代面临的挑战和需要关注的技术，并对在内存处理、分布式、统计等比较流行和实用的技术的应用进行了介绍。     BI的典型结构（typical business intelligence architecture）：       关于BI中涉及的相关技术的概览(思维导图):     关于BI中的CEP：作为不同于传统BI的模式，这篇文章中提到了实时商业智能（Near Real-Time BI）中的一类系统是CEP引擎，通过预定义想要发现的模式在流数据中跟踪实时趋势等（注：这仅仅是rule-based CEP），并讲解了BI中CEP遇到的挑战（Paul Vincent以“ACM Overview of BI Technology misleads on CEP”对这部分进行了点评，纠正了一些对CEP认识的偏差，并特别提到某些所谓需要进行的优化CEP领域已经做得不错了）。     附：两种不同的引擎CEP和搜索结构的比较（对于理解CEP模式很有帮助）： CEP引擎结构（Complex event processing server architecture）： 企业搜索引擎结构（Enterprise search architecture (integrated model)）:

假设对于一个二进制流，我们有一个针对长度为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的个数，则所求的和为：                     [...]

什么时候该使用事件处理？事件驱动性质、事件频率、应用的复杂性、及时性     根据文章When event processing should be use?中引用的使用事件处理的标准：     根据原作结合自己的理解说明判断应用（Application）是否该使用事件处理（Event Processing）的主要标准： 事件驱动性质（Event driven nature）：事件驱动的应用能够从事件处理中获得更多（的收益）。 高事件频率(Event rate)：事件发生的频率越高，利用事件处理技术获益越大； 应用的复杂性(Application complexity)：其实事件计算中很大一块叫复杂事件处理（CEP）。 及时性的需求(Timeliness)：显然，如果并不要求立刻响应，批处理等技术能够挖掘的信息更多，做出的决定会更好。 ===  以上意译+画蛇添足，以下继续凑篇幅 == 外一篇胡扯：事件计算正走向流行       某老师在讲云计算的流行时，提到一项技术流行的S曲线趋势（作为新发现的技术在小范围迅速传播，遭遇要解决的各种问题缓慢增长，积累的量变引起质变获得一个契机井喷，由于盲目应用而遭遇很多失败后退烧，最后技术成熟转向后台，甚至对于研究者也是透明的）：       事件计算的提出已经不下十年，而Yahoo的S4系统的发布催生了近来的事件处理的“大热”——至少从我的部分了解上感觉如此： 在Yahoo的S4的论文中有提到，信息的价值随着时间的流逝而递减，即随着技术发展，会不断向着更快的处理技术发展，趋近于实时处理的技术将越来越重要。信息价值递减曲线（图片来源：The event processing manifest）： 居然在《数据挖掘：概念与技术》中有一章专门讲“挖掘流、时间序列和序列数据”与社会网络分析、图挖掘、空间数据挖掘等并列作为数据挖掘新领域之一。 接上一条，在数据挖掘纠缠不清的机器学习领域：推荐系统高峰论坛上最关注的“推荐系统的影响因素：UI/UE: 40%; data: 30%; domain knowledge: 20%; algorithm: 10%”（报道链接，评论链接），按我的理解如果推荐系统中放入事件处理做出及时推荐的话，或许真的比算法的10%影响大不少。（这一个理由纯凑数，某些准备灌水的同学可以考虑该idea） 偶然得知本科班上某出国的同学（原来是做IR的）居然准备进入该领域，在读一大批该方面的文章； 某所不少与此“完全不搭边”的组拼出人力转过来做事件计算，试图“解决”某些已有的问题； 上文提到的某老师在说云计算时同时提到自己在写某时髦的书时由于忘记，少了一章提一项很重要的研究方向就是事件计算； Yahoo的S4的发布使得流处理获得广泛关注，最值得说明的是一份数据——根据百度统计，本blog访问流量最大的文章是关于S4的论文阅读笔记，最近搜索来源的top20中近30天有8项（全年top中7项）与yahoo的S4平台有关（当然也与我文章比较少很有关系，^_^）：                                         未知的是现在事件计算是应该退烧呢还是还没有井喷？