n-of-N 数据流模型上高效概率Skyline 计算

研究概率数据流上的q-skyline计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N数据流模型.采用将q-skyline查询转换为区间树上刺入查询的方法支持n-of-N数据流模型.提出PnNM算法维护支持n-of-N数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N模型上的q-skyline查询处理.     

基于操作符优先级的两种分布式数据流负载分配算法研究

在分布式数据流中的查询大多表现为连续查询形式,这种查询方式一旦被注册到流系统中后就一直存在,除非特意将其删除.由于流系统中的输入数据是源源不断到来的,因此数据流中的连续查询并不存在传统分布式数据库中查询任务的完成时间概念,反之,它则更关心查询结果的时间延迟.基于此,提出了两种最小化连续查询结果时间延迟的操作符负载分配策略,即PTDM算法和PPLB算法.实验结果表明,相比于其他一些操作符负载分配策略而言,这两种负载分配策略可以有效减小连续查询结果的时间延迟,从而提高分布式数据流的连续查询效率.     

滑动窗口规模的动态调整算法

讨论当数据流系统的数据流流速或连续查询发生变化时,滑动窗口规模的动态调整问题.根据可用内存空间大小和连续查询需求,提出了3类动态调整滑动窗口规模的算法,实现了对连续查询3种服务质量级别的支持,提高了连续查询处理的效率和效果.理论分析与实验结果表明,提出的算法可以有效地应用于数据流系统.     

一种数据流滑动窗口范围连接上基于局部特征的查询索引

在数据流上的连续查询操作中,连接操作是比较重要的一类操作.数据流上数据的变化总体上呈现一个连续性,并且在很多实际的情况下变化是逐渐发生的.数据流系统中的局部性可以表现为数据之间的局部性及连续查询之间的局部性.认为这些特性可以被用来提高数据流系统和应用当中的查询处理性能,尤其是研究相对较少的范围连接.提出的一种基于局部特征的数据流滑动窗口的范围连接索引,充分考虑了用户提交的查询所带有的局部性特征和数据流本身局部性特征,设计了LAQI结构来提高范围连接性能,然后在此基础上提出了LAAQI结构,并针对周期更新滑动窗口提出了范围连接的相应策略.实验证明,这些策略相对于传统范围的连接方法具有很好的性能.     

基于滑动窗口的数据流反向查询方法

提出了一种基于滑动窗口的数据流动态索引方法——DS-索引,采用滑动窗口保存数据流的最新数据,利用AVL树对数据流的变化区间进行索引,有效地解决了数据流的反向查询问题。     

基于滑动窗口的在线数据流增量聚集查询

增量查询技术由于能有效处理大量、快速、源源不断到达的数据流，因此备受关注。滑动窗口是动态数据流环境下的一种典型的窗口类型。该文研究了基于滑动窗口的数据流聚集查询，提出了一种新的增量聚集查询算法，采用了多种增量计算方法和查询共享技术，实现了多窗口资源共享。实验验证了该方法的有效性。     

数据流层次窗口模型及聚集查询算法

本文提出了一种多层次时间窗口模型,支持在不同时段对数据流进行不同粒度的建模,并给出了多粒度聚集树结构及其数据流聚集查询算法,从而有效地解决了在有限时空条件下的数据流聚集查询问题。     

数据流滑动窗口聚集查询降载策略研究*

滑动窗口聚集查询在数据流管理系统中应用广泛,数据流到达高峰期,必须考虑滑动窗口聚集查询中出现的降载问题。分析了子集模型的特点和已有降载策略的不足,给出了数据流滑动窗口聚集查询降载问题的约束条件,提出了能保证子集结果产生的基于丢弃窗口更新策略的降载算法。理论分析和实验结果表明,该算法对数据流滑动窗口聚集查询降载问题的处理具有较高的有效性和实用性。     

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

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

基于数据流的滑动窗口机制的研究

传统的关系数据库是在持久稳定的数据集合上进行数据查询,而数据流的长度是无界的,不可能将所有的数据存储下来,因此对数据流的查询处理大多采用了持续查询。对数据流进行持续查询时,往往感兴趣的不是所有的数据而是最近到达的部分数据,这样就引入滑动窗口模型。定义滑动窗口语义是数据流管理系统中一个非常基础性的工作,直接关系到数据流的存储和查询的执行效率。针对滑动窗口的模型和语义进行了研究。     

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

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

基于结构化P2P的分布式数据流系统的查询处理模型

分析了基于结构化覆盖网的分布式查询处理模型,支持大量数据流的分布式存储,连续查询间、查询内的并行处理操作,能够在很大程度上消除资源约束问题（主要是内存）,提高了查询性能、服务质量,并且该查询模型具有很好的扩展性。     

基于Apache Flink的RDF流数据查询

目前成熟的RDF流处理（RDF Stream Processing, RSP）系统由于集中式的设计而缺乏并行处理特性,因此在查询处理大量传入的RDF流数据时,均无法实现高吞吐和低延迟。为提高查询性能,本文对RSP查询过程和Flink流计算结构进行研究,设计数据源、滤器、多路分区连接和投影4个逻辑操作符,并设计一种多流连接（Multi-Stream Join, MSJ）算法用于生成具有并行性的有向无环图的逻辑查询计划,最后以大数据流处理平台Apache Flink为底层实现逻辑操作符和逻辑查询计划。使用真实数据集SRBench和模拟数据集LUBMs进行实验验证。结果表明,与最成熟的系统C-SPARQL、CQELS相比,单机吞吐量增长高达10倍,5台机器集群的吞吐量增长高达28倍,同时在延时方面达到了毫秒级;在查询性能方面实现了处理大量RDF流数据时吞吐量的提高和延时的降低。     

Generic windowing support for extensible stream processing systems

Stream processing applications process high volume, continuous feeds from live data sources, employ data‐in‐motion analytics to analyze these feeds, and produce near real‐time insights with low latency. One of the fundamental characteristics of such applications is the on‐the‐fly nature of the computation, which does not require access to disk resident data. Stream processing applications store the most recent history of streams in memory and use it to perform the necessary modeling and analysis tasks. This recent history is often managed using windows. All data stream management systems provide some form of windowing functionality. Windowing makes it possible to implement streaming versions of the traditionally blocking relational operators, such as streaming aggregations, joins, and sorts, as well as any other analytic operator that requires keeping the most recent tuples as state, such as time series analysis operators and signal processing operators. In this paper, we provide a categorization of different window types and policies employed in stream processing applications and give detailed operational semantics for various window configurations. We describe an extensibility mechanism that makes it possible to integrate windowing support into user‐defined operators, enabling consistent syntax and semantics across system‐provided and third‐party toolkits of streaming operators. We describe the design and implementation of a runtime windowing library that significantly simplifies the construction of window‐based operators by decoupling the handling of window policies and operator logic from each other. We present our experience using the windowing library to implement a relational operators toolkit and compare the efficacy of the solution to an earlier implementation that did not employ a common windowing library. Copyright © 2013 John Wiley & Sons, Ltd.     

易变数据流的系统资源配置方法

大规模数据流管理系统往往由上层的关系查询系统和下层的流处理系统组成。当用户提交查询请求时,往往需要根据数据流的流速和分布情况动态配置系统参数。然而,由于数据流的易变性,频繁改变参数配置会降低系统性能。针对该问题,提出了OrientStream+框架。设定以用户自定义查询延迟阈值为间隔片段的微批量数据流传输机制;并利用多级别管道缓存,对相同配置的数据流进行批量处理;然后按照数据流的时间戳计算出精准查询结果;引入基于异常检测的增量学习模型,用于提高OrientStream+的预测精度。最后,在Storm上实现了该资源配置框架,并进行了大量的实验。实验结果表明,OrientStream+框架可进一步降低系统的处理延迟并提高系统的吞吐率。     

一种支持流数据的查询语言

流数据的查询应用十分广泛,而标准SQL语言不支持这类查询功能,因此有必要对标准SQL语言进行扩展,以满足流数据的查询应用需求。支持流数据的查询语言StreamSQL在标准SQL语言的基础上增加了对流数据对象的处理机制,通过引入滑动窗口的概念,以支持流数据与关系表的相互转换操作,同时提供用户自定义函数功能,弥补了SQL在流数据处理方面的不足。     

不确定数据流上的并行Skyline查询算法

不确定数据流上的Skyline查询技术逐步引起研究者的关注,传统的集中式流处理算法难以满足海量数据的查询需求,并且云计算所提供的海量计算资源和有效的存储管理模式,为研究并行Skyline查询技术提供了充足的条件。基于上述事实,提出了一种不确定数据流上的并行Skyline查询算法(parallel Skyline over uncertain data streams,PSUDS)。该算法通过交叉划分滑动窗口的方式,将集中式流查询转化为并行处理,以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明,该算法具有较好的并行可扩展性。