Linked-Tree: An Aggregate Query Algorithm Based on Sliding Window over Data Stream

How to process aggregate queries over data streams efficiently and effectively have been becoming hot re search topics in both academic community and industrial community. Aiming at the issues, a novel Linked-tree algorithm based on sliding window is proposed in this paper. Due to the proposal of concept area, the Linked-tree algorithm reuses many primary results in last window and then avoids lots of unnecessary repeated comparison operations between two successive windows. As a result, execution efficiency of MAX query is improved dramatically. In addition, since the size of memory is relevant to the number of areas but irrelevant to the size of sliding window, memory is economized greatly. The extensive experimental results show that the performance of Linked-tree algorithm has significant improvement gains over the traditional SC （Simple Compared） algorithm and Ranked-tree algorithm.

A graph-based sliding window multi-join over data stream

Join operation is a critical problem when dealing with sliding window over data streams. There have been many optimization strategies for sliding window join in the literature, but a simple heuristic is always used for selecting the join sequence of many sliding windows, which is ineffectively. The graph-based approach is proposed to process the problem. The sliding window join model is introduced primarily. In this model vertex represent join operator and edge indicated the join relationship among sliding windows. Vertex weight and edge weight represent the cost of join and the reciprocity of join operators respectively. Then good query plan with minimal cost can be found in the model. Thus a complete join algorithm combining setting up model, finding optimal query plan and executing query plan is shown. Experiments show that the graph-based approach is feasible and can work better in above environment.

Incremental Data Stream Classification with Adaptive Multi-Task Multi-View Learning

With the enhancement of data collection capabilities,massive streaming data have been accumulated in numerous application scenarios.Specifically,the issue of classifying data streams based on mobile sensors can be formalized as a multi-task multi-view learning problem with a specific task comprising multiple views with shared features collected from multiple sensors.Existing incremental learning methods are often single-task single-view,which cannot learn shared representations between relevant tasks and views.An adaptive multi-task multi-view incremental learning framework for data stream classification called MTMVIS is proposed to address the above challenges,utilizing the idea of multi-task multi-view learning.Specifically,the attention mechanism is first used to align different sensor data of different views.In addition,MTMVIS uses adaptive Fisher regularization from the perspective of multi-task multi-view learning to overcome catastrophic forgetting in incremental learning.Results reveal that the proposed framework outperforms state-of-the-art methods based on the experiments on two different datasets with other baselines.

Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows

Detecting duplicates in data streams is an important problem that has a wide range of applications. In general, precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios, and, on the other hand, the elements in data streams are always time sensitive. These make it particular significant approximately detecting duplicates among newly arrived elements of a data stream within a fixed time frame. In this paper, we present a novel data structure, Decaying Bloom Filter （DBF）, as an extension of the Counting Bloom Filter, that effectively removes stale elements as new elements continuously arrive over sliding windows. On the DBF basis we present an efficient algorithm to approximately detect duplicates over sliding windows. Our algorithm may produce false positive errors, but not false negative errors as in many previous results. We analyze the time complexity and detection accuracy, and give a tight upper bound of false positive rate. For a given space G bits and sliding window size W, our algorithm has an amortized time complexity of O（√G/W）. Both analytical and experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results.

Continuous Outlier Monitoring on Uncertain Data Streams

Outlier detection on data streams is an important task in data mining. The challenges become even larger when considering uncertain data. This paper studies the problem of outlier detection on uncertain data streams. We propose Continuous Uncertain Outlier Detection （CUOD）, which can quickly determine the nature of the uncertain elements by pruning to improve the efficiency. Furthermore, we propose a pruning approach -- Probability Pruning for Continuous Uncertain Outlier Detection （PCUOD） to reduce the detection cost. It is an estimated outlier probability method which can effectively reduce the amount of calculations. The cost of PCUOD incremental algorithm can satisfy the demand of uncertain data streams. Finally, a new method for parameter variable queries to CUOD is proposed, enabling the concurrent execution of different queries. To the best of our knowledge, this paper is the first work to perform outlier detection on uncertain data streams which can handle parameter variable queries simultaneously. Our methods are verified using both real data and synthetic data. The results show that they are able to reduce the required storage and running time.

Efficient Processing of Skyline Group Queries over a Data Stream

In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least one attribute. If an object cannot be dominated by any other object, it is a skyline object. The skyline group problem involves finding k-item groups that cannot be dominated by any other k-item group. Existing algorithms designed to find skyline groups can only process static data. However, data changes as a stream with time in many applications,and algorithms should be designed to support skyline group queries on dynamic data. In this paper, we propose new algorithms to find skyline groups over a data stream. We use data structures, namely a hash table, dominance graph, and matrix, to store dominance information and update results incrementally. We conduct experiments on synthetic datasets to evaluate the performance of the proposed algorithms. The experimental results show that our algorithms can efficiently find skyline groups over a data stream.

A domain-independent methodology to analyze IoT data streams in real-time.A proof of concept implementation for anomaly detection from environmental data

Pushed by the Internet of Things(IoT)paradigm modern sensor networks monitor a wide range of phenomena,in areas such as environmental monitoring,health care,industrial processes,and smart cities.These networks provide a continuous pulse of the almost infinite activities that are happening in the physical space and are thus,key enablers for a Digital Earth Nervous System.Nevertheless,the rapid processing of these sensor data streams still continues to challenge traditional data-handling solutions and new approaches are being requested.We propose a generic answer to this challenge,which has the potential to support any form of distributed real-time analysis.This neutral methodology follows a brokering approach to work with different kinds of data sources and uses web-based standards to achieve interoperability.As a proof of concept,we implemented the methodology to detect anomalies in real-time and applied it to the area of environmental monitoring.The developed system is capable of detecting anomalies,generating notifications,and displaying the recent situation to the user.

医院大数据平台建设难点及关键技术研究

目的解决医院大数据平台在数据采集、治理及应用环节面临的困难。方法总结建设大数据平台的经验,深入分析该平台在各环节的建设难点,提出“流批一体”数据处理、“湖仓一体”存储、存算分离等关键技术方案。结果该平台已接入医院34个业务系统数据、超过3PB的基因组学数据,提供超过2500TFLOPS的算力资源,为医院临床诊疗、管理决策、临床科研提供应用服务。结论以应用为驱动的大数据平台逐步实现了医院数据资产的统一存储和集中管理,有助于推动大数据技术在医疗领域的应用和发展。

IoT感知的业务微流程建模

基于物联大数据赋能的业务流程能够更快更准地感知物理世界并及时做出响应的需求突现,提出一种物联网(Internet of Things,IoT)感知的业务微流程建模方法。首先,以单个IoT对象为中心建模,融合MAPE-K(monitor,analysis,plan,execution and knowledge base,MAPE-K)模型思想,将IoT对象实例生命周期的行为状态与微流程实例状态一一映射,实现对单个IoT对象的环形自动监控和调节;其次,基于从IoT传感设备获取的数据,定义基于SASE+语言的业务规则,提取对业务流程有意义的业务事件,避免了无关事件对宏流程的干扰;最后,通过设计一个微流程建模工具原型系统,结合真实案例分析,验证了提出建模方法的有效性,实现了业务流程与IoT实时流式感知数据的结合,并显著减少了宏流程需要处理的业务事件数量。

Continuous query scheduler based on operators clustering

Data stream management system (DSMS) provides convenient solutions to the problem of processing continuous queries on data streams.Previous approaches for scheduling these queries and their operators assume that each operator runs in separate thread or all operators combine in one query plan and run in a single thread.Both approaches suffer from severe drawbacks concerning the thread overhead and the stalls due to expensive operators.To overcome these drawbacks,a novel approach called clustered operators scheduling (COS) is proposed that adaptively clusters operators of the query plan into a number of groups based on their selectivity and computing cost using S-mean clustering.Experimental evaluation is provided to demonstrate the potential benefits of COS scheduling over the other scheduling strategies.COS can provide adaptive,flexible,reliable,scalable and robust design for continuous query processor.

面向流数据的多离群点检测算法研究

离群点检测是数据管理领域中的一个重要问题,在信用卡欺诈检测、工业工程过程管理、银行数据处理等方面等均有广泛应用.大数据时代的到来加剧了对大规模流媒体数据进行离群点检测多样化的需求,不同用户可根据自身偏好选择不同类型的数据作为离群点.针对流数据环境下多离群点检测问题,提出了一种查询处理框架MQOD(Multiple Query of Outlier Detection),利用多查询任务之间的包含关系来支持多离群点检测任务,从而提高查询效率.在MQOD框架下,构建了HT-Grid索引以支持流数据的管理,利用滑动窗口的时间特性对窗口进行划分,并根据划分结果确定执行查询的范围,减少不必要的对象访问.通过真实数据集和合成数据集对MQOD算法进行了验证,验证结果表征了算法的高效性.

数据流技术在电网自动化中的应用研究

对近年来信息技术领域提出的数据流技术在电网自动化中的应用进行了充分探讨,目的是利用信息技术来尽可能地提高电网的自动化水平。给出了包含传感与量测、实时数据分析处理和在线决策3个环节的用于实现电网自动化的闭环过程,阐述了用数据流技术和数据流系统实现其中的实时数据分析处理环节的具体方法。对智能电网环境下便于提高智能电网自动化水平的实时数据处理架构进行了展望。

不确定数据查询技术研究

当前不确定数据广泛存在于诸如传感器网络、RFID网络、基于位置服务以及移动对象管理等各种现实的不确定性应用中.不确定数据查询作为不确定数据管理的重要组成部分,在信息检索、数据挖掘、决策制定和环境监控等众多应用中发挥重要作用,目前已成为数据库和网络计算等领域的一个研究热点.从目前不确定数据查询研究的各种查询类型介绍和查询特点分析出发,主要综述了4种典型的不确定数据查询类型,即不确定Skyline查询、不确定Top-k查询、不确定最近邻(NN)查询以及不确定聚集查询;重点论述了各种不确定数据查询的定义,各类查询的特点,并分类介绍了当前各类不确定数据查询研究的现状和各种查询方法的优缺点;最后,基于当前不确定数据查询技术的最新研究动态指出了未来研究工作的趋势.

基于滑动窗口的数据流连续J-A查询的处理方法

数据流滑动窗口连接聚集连续查询(简记J-A查询)是经常使用的一类查询.这类查询的直观处理方法是创建查询操作树,以流水线的方式计算查询结果.这种方法需要在主存中保存滑动窗口连接的结果,查询处理的主存空间开销为Ο(α×β),其中α,β为参加连接两个滑动窗口的大小.在数据流的查询处理中,内存是最重要的计算资源.提出了两种滑动窗口J-A连续查询处理算法——IC算法和TC算法,使得查询处理的空间开销降为Ο(α+β).理论分析和实验结果表明,所提出的算法具有更高的效率.

配电自动化的数据流管理系统设计

数据采集与监视控制(SCADA)系统采集的各种实时、连续、有序的值序列是典型的数据流,而目前SCADA系统所采用的实时数据库系统对数据流处理的实时性和自适应性要求尚需改进。文中以配电自动化管理为应用背景,提出一个支持配电自动化的数据流管理系统,在配电网远方终端加入查询处理层,降低网络传输负载,提高配电网数据处理的实时性和可靠性。文中描述了系统的基本结构、各组成部分的功能和关键技术,探讨了有关分布式连续查询处理、近似计算、归档数据处理等问题,并提出在数据流研究方面的一些新看法。

面向无线传感器网络的流数据压缩技术

目前无线传感器网络广泛应用在各个领域来进行复杂的监控和计算任务。因其资源有限的特点(处理、传输带宽、能量),对无线传感器网络在数据处理和传输方面提出了新的挑战。本文提出一种基于曲线拟合技术的流数据的压缩传输方法CODST,用于压缩每个传感器采集到的数据,并在基站进行数据还原。实验表明,提出的方法在保证压缩传输后的流数据的精度前提下可以大大减少数据传输量,节省网络带宽和能量。

不确定Skyline查询技术研究

当前不确定数据广泛存在于诸如传感器网络、RFID网络、基于位置服务、移动对象管理网上购物和市场监控等各种实际应用中.不确定Skyline查询作为不确定数据管理的一个重要方面,由于其在决策制定、市场分析、环境监控和数据挖掘等方面的重要作用,近年来在数据库和网络计算领域受到广泛关注.首先,概述了各种不确定数据类型上的Skyline查询定义,包括离散、连续概率分布模型以及不完全数据上的Skyline查询定义;其次,分析了不确定Skyline查询的特点,并在此基础上综述了现有的各种不确定数据集上的集中式和分布式Skyline查询方法,重点分析了各种算法的原理和优缺点;再次,介绍了不确定数据流上的Skyline查询定义并综述了各种不确定数据流上的Skyline查询方法;最后,基于最新研究动态指出了未来不确定Skyline查询研究的趋势.

基于滑动窗口的数据流压缩技术及连续查询处理方法

基于滑动窗口的连续查询处理是数据流研究领域的一个热点问题 已有的研究工作均假设滑动窗口内的数据能够全部保存在主存中 ,若滑动窗口内的数据量超过了可用主存空间 ,已有的查询处理方法则无法正常工作 提出两种数据流上的滑动窗口压缩技术 ,有效地降低了滑动窗口的存储空间需求 同时 ,给出了基于压缩滑动窗口的连续查询处理算法 ,理论分析和实验结果表明 ,这些算法具有很好的性能 。

无线传感器网络数据管理技术

无线传感器网络主要应用于环境监控,需要对网络运行过程中产生的大量数据进行有效的管理,从而提高网络性能。该文讨论无线传感器网络数据管理技术的发展情况,分析传感网中的数据管理与传统分布式数据库管理的区别,总结在传感网中进行数据管理的关键技术和难点,介绍各项关键技术的进展,指出传感网数据管理技术面临的挑战和研究方向。

分布式数据流关系查询技术研究

随着在线分析连续数据流的需求日益增多,用于实时处理海量、易变数据的数据流管理系统由此产生.大数据时代下,随着开放式处理平台的发展,为处理大规模且多样化的数据流,出现了若干分布式流处理系统,如S4、Storm、Spark Streaming等.然而,为提升处理系统的易用性和处理能力,需要在其之上构建具有抽象查询语言的关系查询系统,以构筑完整的分布式数据流管理系统.如何设计并实现高效易用的关系查询系统是一个亟待解决的问题.文中首先概述了分布式数据流查询处理的典型应用、数据特征和实现目标.进而,提出了分布式数据流关系查询系统的基础架构,并基于此架构深入分析了用户自定义函数查询、查询优化、驱动方式、编译技术、算子管理、调度管理和并行管理等关键技术.然后,对比分析了SPL、StreamingSQL、Squall和DBToaster这4种具有代表性的查询系统实例.最后,指明了该技术在优化技术、执行策略、实时精准查询和复杂查询分析等方面所面临的挑战和今后的研究工作.