【摘 要】
：
数据流的应用,例如网络监测、在线实时交易分析、入侵检测、传感器网络等为现有的传统数据库系统带来了很大挑战.与以往固定容量的数据集不同,无界且连续的数据流需要特殊的处理技术.在数据流处理领域的研究已经取得了可观的进展.比较著名的数据流系统有Aurora,STREAM,NiagaraCQ以及TelegraphCQ.对于处理连接(join)这一常用的操作符来说,由于流的无界性,将一个流中的每个元组和另一
【机 构】
：
东北大学计算机科学系,沈阳,110004
【出 处】
：
第二十三届中国数据库学术会议(NDBC2006)
论文部分内容阅读
数据流的应用,例如网络监测、在线实时交易分析、入侵检测、传感器网络等为现有的传统数据库系统带来了很大挑战.与以往固定容量的数据集不同,无界且连续的数据流需要特殊的处理技术.在数据流处理领域的研究已经取得了可观的进展.比较著名的数据流系统有Aurora,STREAM,NiagaraCQ以及TelegraphCQ.
对于处理连接(join)这一常用的操作符来说,由于流的无界性,将一个流中的每个元组和另一个流中的每个元组一一比对是不可行的,因而引入了滑动窗口技术,即用一个有容量限制的窗口将参与连接的元组限制在最新的一系列元组中,得到用户可接受的近似连接结果.滑动窗口主要有两种形式:基于时间的窗口及基于元组的窗口.本文重点考虑基于元组的窗口.需要注意的是即使引入滑动窗口,对连接操作符的处理仍有可能造成CPU及内存资源的不足.因此在这种情况下有必要对数据流进行卸载,即抛弃数据流中的部分元组以降低系统的负载,从而加快连接操作的处理速度,保持系统与不断更新的数据流同步,不致产生因等待而出现的查询质量变差的情况.
本文提出了一种新的卸载策略以使过载数据流上的滑动窗口连接操作可以输出最大子集结果.通过双窗口模型和辅助窗口上的统计信息,我们可以对近期元组的连接结果进行预测,并通过后端卸载实现元组的语义选择.当流速过快时,又引入前端卸载,通过这种前后端卸载相结合的策略能够有效的实现过载状况下的连接结果输出最大化。
其他文献
离群数据挖掘与分析在许多领域的重要性已经日益体现,特别在安全领域对此项技术的实时性要求较高,而离群对象的关键域子空间对于进一步分析数据对象的离群原因具有指示作用,因此如何更快地获取离群数据集的关键域子空间成为一个十分重要的研究内容.本文以探索性数据分析方法为基础,通过分析数据对象个体离群与其属性值离群之间的关系,提出了一种高效实用的关键域子空间实时搜索算法RSKAS,实验证明,这种方法对于问题规模
本文提出了一种在数据流中挖掘频繁闭项集的方法.应用定量更新滑动窗口策略,解决了批处理方法中时间粒度较粗的问题,结合时间窗口,对历史数据进行保存,能够支持对给定时间段内频繁闭项集的频繁计数进行查询.本文设计了CFIT数据结构,通过结点的ChildLinks能够快速检查本结点是否为频繁闭项集,降低了频繁闭项集挖掘算法的复杂性.通过TW-CFI算法可以对到来的事务进行定量处理,灵活适应数据流中的多变性.
本文讨论数量关联规则挖掘过程中连续属性离散化问题,结合k度完全的思想合并和分裂传统的最近邻聚类算法的结果来离散化连续型属性,这种方法既考虑数据稀疏性,体现数据的真实分布,又结合关联规则本身的特点重新调整改善聚类结果,有效降低出现过小支持度和过小置信度的可能,对于数量关联规则挖出有效的规则有重要的应用价值,当然,类间距离的阈值不好确定,还有待进一步研究。
联机分析处理(OLAP)系统是数据仓库主要的前端支持工具,它给用户提供了交互的、多维的、多角度的数据结果展示方式.数据仓库一般存储了大量历史数据,因此如何通过建立有效的OLAP模型、有效地实例化数据立方体(Cube)来提高OLAP系统查询响应速度是近年来数据仓库领域研究的一个热点.然而对于一些特殊需求的OLAP分析来说,依靠现存的OLAP构建模型无法对Cube进行预先实例化.例如,业务需要对w度量
本文针对普通用户自然语言提出查询请求,结合XML文档检索的新特征,分析了XML文档中自然语言查询的模糊内容和结构检索结果排序的影响因素.充分利用答案结点的逻辑意义完整性,在追求查准率的前提下力求提高查全率,主要表现在以下三个方面:(1)从自然语言查询中抽取路径信息的模糊处理;(2)利用预设答案结点解决查询粒度过小的问题(内容放松);(3)模糊路径匹配(即结构放松)。
数据流具有快速、大量、连续、随时间变化等特性,使得流数据无法完整地保存在存储介质中.而复杂的聚集计算需要对数据进行多趟扫描来获得精确查询结果,这在数据流的处理上造成了很大的困难.因此在用户接受范围内,使用一趟算法获得一个近似的聚集结果的技术就成为了研究热点.直方图在数据流处理中通常用于保存大纲数据结构.目前许多数据流管理原型系统中多采用直方图、小波变换、数据写生、随机抽样等方法来保存大纲数据.直方
执行计划缓存的主要功能避免相同查询的重复优化.当前的三大主流商业数据库中都支持执行计划共享.SQL Server将SQL或T-SQL执行计划保存到过程缓存中.Oracle将查询执行计划保存到库缓存中,通过V$LIBRARYCACHE动态性能视图可以查看库缓存使用情况.DB2将查询执行计划保存到全局包缓存pkgcachesz中.本文以PostgreSQL为基础,构建了一个可运行、可验证的原型系统.在
随着传感器技术、与低功耗无线通信技术的发展,生产具备无线通信以及信息处理能力的微型无线传感器已成为可能.由于传感器节点能量有限,因此如何在尽量减少能量消耗,是目前连续查询面临的一大挑战.本文提出了一种基于动态线路的连续查询处理(Adaptive Itinerary based Window Query Execution)的方法.将查询区域划分成一些小的子区域;从子区域中挑选代表节点;相邻子区域内
Rails框架是一个非常新、令人兴奋的Web程序自动生成框架.该框架在Web社区中已经引起了人们相当的兴趣.它的核心架构虽然仍然遵循在J2EE中发现的基本模式,但由于建立框架时采用了许多命名习惯自动生成简洁、清楚的代码而不是配置文件,所以可以说Rails动了J2EE的奶酪已经成了不争的事实.在数据库方面,Rails框架的默认的CRUD等行为可以简洁到只需要一行代码.这种无编码的实现CRUD型的应用
Model-Driven Architecture(MDA)是由OMG组织于2001年2月提出的用模型技术进行软件系统开发的方法和标准体系,它代表了现代软件开发理论与方法发展的主流趋势.可以预见它会成为继面向对象技术后软件工程史上又一个里程碑.MDA的核心思想是,首先为企业商业应用建立独立于实现技术的平台无关模型(platform-Independent Model,PIM),再通过映射方法将平台