分布式数据流连接查询算法

分布式处理是数据流管理系统发展的必然趋势。文章研究了分布式数据流的连接查询，提出DM3Join算法，它由2部分组成：一是通过分解并发的连接请求，合并相同的连接谓词，形成分布式查询操作算子；二是数据流在各分布式代理(Agent)中流转实现部分连接，并在查询引擎处组合成最终结果。DM3Join算法采用了一种类似路由表的结构执行窗口连接，由于可以共享中间结果，算法只需扫描数据1遍。分析和实验证明，该连接算法是高效的。     

数据流技术及查询算法研究

数据流技术是一种正在兴起的新型数据形式,信息以数据序列的形式产生并且需要实时、持续地进行处理。数据流管理系统(DSMS)是面向数据流而设计的数据管理系统,它能有效地处理输入流数据并提供持续检索的功能。本文从整体上介绍数据流的相关技术,重点分析了DSMS的特点以及相应的查询算法的分析。     

一种基于优先级的数据流查询实时调度策略

针对一些高关键性的特殊应用，把传统实时系统中的截止期、空闲时间、关键性等概念引入数据流管理系统，根据系统中连续查询的特征，赋予其新的涵义。提出了一种基于优先级的实时调度策略，使得流截止期较早、空闲时间较短、关键性较高的查询具有更高的优先级；给出了一种优先级树结构，使得基于优先级的查询执行序列唯一化。实验表明该策略提高了连续查询的实现价值率和连续查询调度的成功率。     

一种事件驱动的数据流查询模型

分析数据流上事件的语义和特点,建立了事件驱动的数据流模型EQM.提出一种具有事件监控,事件定义和事件驱动功能的语言EQL,讨论了事件监控和事件驱动查询的优化算法以及相关的效率问题和实时性.实验表明,该模型在解决数据流上事件相关问题比现有的数据流模型和处理方法有着更好的性能.     

高效处理分布式数据流上skyline 持续查询算法

基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式算法BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline 增量的计算等进行了系统优化,使算法在通信负荷与反应延迟上达到了较好的综合性能.理论分析证明,在所有基于非 共享策略的算法中,BOCS 算法通信最优.大量的对比实验结果也表明,所提出的算法高效、稳定且具有良好的可扩展性.     

分布式数据流查询方案及优化

流式数据库系统是一种新型数据库系统,方便于执行连续数据流查询。许多基于流的应用都是分布式的, 由于输入流速率及其他系统参数如可用的计算资源是易变的,所以一个流查询方案必须能适应这些变化。 提出一种分布式流查询方案并进行了优化,使用元组响应时间及系统吞吐量来评价方案的性能。同时,通过实验和其他方案进行比较,证明了方案是最佳的。     

数据流中一种适应性查询优化方法

对数据流中的查询处理机制进行了深入的研究,从内存使用量和查询的实时性两方面进行综合考虑,提出了一种基于多因素的动态查询优化及调度策略MultiFactor,它根据各操作符消耗系统中元组数量的快慢来动态调整操作符调度次序,按查询的截止时间来确定各操作符调度时间,同时提出了多流连接查询的调度方法。给出了Multi-Factor适应性优化的时机以及调整策略。     

一种基于滑动窗口的数据流相似性查询算法

相似性查询是一种非常重要的数据挖掘应用。由于数据流具有无限、高速等特性,传统的查询算法不能直接应用于数据流。提出了一种基于小波滑动窗口的多数据流相似性查询算法。算法首先将滑动窗口划分成若干等宽基本窗口,然后对每个基本窗口内的数据进行小波分解与系数约简,从而形成小波摘要窗口。执行相似性查询时,直接基于小波摘要进行计算,而无需数据重构。由于利用了小波分解的线性处理优点,算法具有较低的时间复杂度。最后,基于实际数据对算法进行了实验,实验结果证明了算法的有效性。     

分布式数据流增量聚集

分布式处理是数据流管理中的主流技术,聚集是分布式数据流系统中一种重要的连续查询类型.在分布式数据流环境中,由于需要连续计算聚集值,并且在分布式网络中连续传送聚集值,导致系统的通信开销非常大.为了有效地减少网络中数据流的传输量,提出了一种近似增量聚集算法(approximately incremental aggregate over distributed data stream,AIADDS).算法增量地计算网络中各个站点的聚集值,只有当聚集值的改变超出给定的阈值才向其他站点传送聚集改变量,这样,可以显著地降低网络的数据传输量.作为算法核心的VSB-Tree能够有效地合并、存储来自孩子站点的聚集值,同时增量地向它的父站点传送聚集改变量.理论分析和实验结果表明,算法是行之有效的.     

一种数据流查询共享模型的设计

为了提高查询效率,从数据流查询过程中查询操作单元和查询存储结构的共享两个方面展开研究.设计一种基于共享的二级索引队列,用于存储数据流中间结果.该结构使得中间查询结果可以再利用的同时也为数据共享情况下的迁移提供了一定的灵活性.对于多查询共享,通过抽取相同数据流中的相同谓词进行查询共享,实现一处计算多处使用的目的.最后对相关模型和算法进行了分析.     

基于下推自动机的XML数据流递归查询研究

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型.由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询.实验结果表明,该算法在性能上要优于传统方法.     

数据流多连续查询优化技术

根据数据流连续达到、大小无界和实时性强的特点,引出数据流多连续查询的基本概念.针对多连续查询的特点和用户的需求,将多连续查询优化技术分为单流多查询和多流多查询.详细论述了单流过滤型多连续查询优化技术和基于共享的多流多连续查询优化技术,通过全面系统地分析每种优化算法的基本思想,得出每种查询技术的优缺点及适用场合.     

面向不确定数据流的近似ER-Topk查询处理

随着移动互联网的快速发展以及信息技术的普遍应用,在许多应用中都产生了海量、不确定性数据,包括金融、军事、位置服务、医疗以及气象等。然而,传统的确定性数据管理方法很难管理不确定数据,亟需开发新型数据管理方法。可能世界模型被广泛用于为不确定数据建模,通过该模型可以衍生出诸多确定性的可能世界实例。不确定性数据流是指高速到达的海量不确定元组序列,因而不确定数据流管理比不确定性静态数据管理更具挑战性。面向于不确定数据流的ER-Topk查询是一个典型问题,但是处理复杂度高。提出一种近似算法来处理该查询,具有较小的空间复杂度;同时,还通过搜索策略优化来进一步提升查询处理效率。实验结果验证了所提方法的有效性和高效性。     

面向数据流离线分析的无共享并行查询中间件研究

通过分析网络监控离线分析处理的负载特征,给出了一种面向数据流离线分析处理的并行多策略查询中间件,并利用多策略及DBMS实现了局部结果的汇总,对需后处理查询的系统扩展性、不需后处理查询的系统扩展性分别进行了评价分析。评价分析结果表明:提出的基于面向数据流离线分析处理的并行多策略查询中间件,不但做到了中间件的轻量级,实现了查询内部的并行化;同时,能利用多策略及DBMS实现子节点间并行查询,能提高查询的响应时间,从而在多节点时保持较好的扩展比,避免了系统过载,提高了资源利用率。     

HoliAdapt——数据流中一种适应性查询处理策略

针对数据流上连续查询处理的特征,我们从选择率和执行时间的角度出发,考虑内存使用量和输出延迟适应性因素,提出一种适应性的查询处理策略—HoliAdapt。该策略基于查询窗口动态地收集统计信息,利用数学方法不断地优化查询计划,通过核心调度方法,对操作符进行适应性的调度,有效地减少时间延迟和内存使用量,提高系统查询的效率。     

关联数据分布树在分布式查询中的应用

连接操作是影响分布式查询性能的关键因素,数据存储是影响连接操作的重要因素.为了提高分布式系统的查询性能,通过研究数据之间的关系,提出一个关联数据分布树.利用该关联数据分布树来构造一系列的关联元组集合,然后按照各个站点的负载能力,把这些关联数据集合分配给相关站点.实验结果表明,当多个关系频繁的进行连接操作时,关联数据分布树能有效地提高整个分布式系统的查询性能.     

基于时间倾斜的数据流聚集压缩算法

对于许多应用领域不断产生的数据流,面向数据流聚集查询的应用最为广泛。本文在构造压缩桶的基础上,提出了基于时间维度压缩数据流的算法,来动态地形成压缩数据流,并进一步给出了使用压缩桶获得数据流聚集查询的数学方法。     

分布式流数据频繁项发现算法的研究

对分布式流数据中频繁项的发现算法进行了研究,利用一种新颖的分布式概要算法(DSA)来发现从叶子节点直至根节点的概要结构,通过在不同的分布状态下设置相应的精确梯度来最小化通信负载,并利用真实数据集验证了该结构和算法的有效性。     

一种改进的分布式数据流查询操作放置算法

在分布式数据流管理系统中,需要将查询操作放置到不同的处理结点执行。因此,如何放置查询操作成为分布式数据流管理研究的核心问题。Peter等人提出一种基于时延空间和弹簧张弛技术的查询操作放置算法,但是该算法假设查询操作之间数据流的流速不变,没有考虑数据流的流速与数据流查询操作之间的相关性。为此,通过分析不同的数据流查询操作与其输出的数据流的流速之间的关系,对Peter等人提出的算法加以改进,实验结果表明,改进后的算法可以有效地应用于分布式数据流管理系统。