数据流连续查询处理技术的研究

数据流查询处理技术的研究是目前数据库研究领域的热点问题.传统的数据库技术不能处理诸如网络监测、传感器网络、股票分析等应用中所生成的新型数据,即数据流.数据流作为一种新的数据形态,不同于传统的静态数据,具有连续快速、短暂易逝、规模宏大和不可预测的特点;其研究核心是在一个远小于数据规模的有限存储空间迅速获得近似查询结果.综述关于数据流查询处理技术的研究成果,主要介绍数据流模型、查询的特征、数据流近似查询操作算法的实现以及数据流系统中的查询处理方法.     

一种基于混沌理论的数据流连续聚集查询预测算法

为了有效地预测聚集查询的未来聚集值,提出了一种基于混沌理论的数据流连续聚集查询预测未来聚集值算法——CSPA算法.数据流看作是以数据到达时间为序的一个时间序列,借鉴传统时间序列分析技术探讨了连续聚集查询的未来聚集值预测问题,但由于数据流序列与传统时间序列在时间间隔和数据集的处理上存在很大差别,于是采用流滑动窗口技术加以处理.其次,针对目前数据流聚集查询预测领域已有的一些研究结果都未考虑流数据内在的复杂非线性动力学特征对预测的影响问题,该算法又利用了混沌理论中的局域预测思想解决了这一不足.实验结果表明,利用该算法进行预测具有很好的准确性.     

基于直方图的数据流降载策略研究

提出了基于直方图的降载策略,能很好地减缓在过载发生时系统性能的下降.降载的目标在于删除过载数据的同时尽可能地保持数据流的特征.为了处理大量被延迟的数据,构建了一种塔形矩阵的数据存储结构,利用其对过载数据分桶,每桶提取一个代表数据并删除该桶中其余数据,将每个桶的代表数据组成新的数据流参与查询操作.实验结果表明:这种降载方法能有效减少系统负担,生成的新数据流参与数据流查询后所得查询结果错误率较低,其性能优于其他已有算法.     

基于混合处理模型的乱序数据流分布式聚合查询处理技术

为了解决现有的乱序数据流聚合查询处理技术不能在降低查询处理延迟,同时保障聚合查询结果的最终正确性的局限性问题,本研究设计了混合嵌入分布式流处理模块和分布式批处理模块的乱序数据流分布式聚合查询处理技术。该技术一方面基于用户给定的结果质量,限制自适应地优化流处理模块所用的缓冲区大小,从而尽可能降低流处理的查询处理延迟;另一方面基于备份于分布式数据存储系统的历史流数据,并以批处理的方式实现对极其晚到流元组的查询处理,从而保障聚合查询结果的最终正确性。基于真实的乱序数据流数据集对该技术进行测试分析表明:该技术在平均查询处理时延、查询结果精度和系统可扩展性方面,比目前最好的基于缓存的乱序数据流处理技术均具有显著优势。     

基于OpenMP的并行集合包含查询算法

集合包含查询分为子集、等值和超集3种查询,在多个领域有重要的研究意义和应用价值.随着集合数据集规模的不断增大,迫切需要提高集合包含查询的效率.集合包含查询并行化是解决这一问题的一条途径,基于OpenMP提出并行子集、等值和超集查询算法,这些算法采用反向索引结构,通过for循环并行化实现查询间的并行执行.为提高算法效率,设计2个高效的并行共享数据结构:1PVEC结构:用于存储并行查询结果.2CountArr数组:针对超集查询,用于对反向列表中的元素计数,并行线程可异步地对这两个结构进行访问.在MSWEB和DBLP 2个数据集上进行扩展实验,结果表明,实现的3种并行集合包含查询具有较高的效率,对3种查询在MSWEB数据集上均可达到4X以上的加速比.     

数据流系统中的查询处理机制

近年来,一种数据密集型的应用得到了广泛的关注。在这种应用中,数据不再来自于存储在永久介质上的数据库,而是以大量的、连续的、快速的、随时间变化的、无边界的数据流的形式到达。本文论述了当前数据流的产生背景、研究现状并且针对数据流应用中的种种特征,对数据流中的查询处理机制进行了深入讨论,包括查询分类、查询的特点及数据流系统中查询的处理方法。     

移动环境中的位置依赖连续轮廓查询

针对移动环境中查询点快速移动时连续、高效输出给定搜索区域数据轮廓的问题,提出一种位置依赖连续轮廓查询算法(LDCS).该算法结合数据流技术,首先使用R树快速更新查询数据,然后利用两次连续计算时搜索区域的重叠性构造被动数据流,并对新增和失效数据分别进行处理,从而连续输出轮廓.由于充分利用了已有结果,LDCS的计算量较传统算法有大幅下降.实验结果表明,LDCS特别适合计算频度要求较高的场合,与基于网格索引的算法相比,时间效率随着数据集规模的增大显著提升.     

数据流处理系统的负载控制策略研究

在高速网络数据流查询处理系统中,数据到达可能是突发性的,对数据流的实时查询处理要能适应数据流的特性和网络的波动环境,应用闭环控制理论进行系统负载控制,充分利用系统资源,在系统过载时降低存储需求,提高适应性和精确度.     

基于数据流的时间条件占优查询

传统的偏好推理使用权衡增强的条件偏好网络（Tradeoff-Enhanced Conditional Preference Networks,TCP-nets）进行用户的偏好推理，不仅能高效地表示对元组的定性偏好关系并优化用户偏好结果，还能描述每个属性之间的偏好关系，其主要聚焦于关系元组中的单个属性的偏好.但把对条件偏好查询的技术推广到数据流的条件提取却是一个挑战，面临的技术困难主要是对数据流中序列的提取，对提取的序列进行占优查找等.首先，针对偏好数据流，提出一种时间条件查询语言Stream Pref来处理数据流；其次，在Stream Pref中加入时间索引来推理和规范数据流提取序列的时间条件偏好，提出提取对象序列算法、占优对象及占优序列查找算法和数据流序列间占优对比的算法；最后，在数据集上分析验证提出的算法的有效性.实验结果证明，提出的算法与min Top-k,Partition和Incpartition算法相比，得到的结果更准确.     

数据流管理系统关键技术研究

传统数据库系统用于需要持久稳固的数据存储和复杂查询的应用,然而近几年许多的应用证明这种数据模式和查询范例是不适合的,如传感器数据位置跟踪、工厂装配线管理、金融证券管理、Internet流量监控、Web使用日志、电话呼叫记录、和事务日志的在线分析等,在这些应用背景中信息按照数据值序列的形式自然产生,都需要及时地处理大规模的潜在快速的异步的数据流.本文回顾近来数据流管理系统领域的相关工作和流项目的研究情况;分析了连续查询处理的新需求和挑战;重点研究包括数据模式,系统结构,连续查询语言,调度方法,相关算法和查询评价等关键技术.     

数据流上基于遗传算法的并行查询优化技术

传统数据库中存储的是相对静态的记录集,这些记录没有预先定义的时间概念,除非时间属性被显示地加上去.虽然这个模型能够较好地表示商业数据库和个人信息存储库,然而它对快速变化的数据流进行在线分析的支持存在很多限制.因此,需要对已有技术进行扩展研究,构建出新的管理系统来管理数据流.数据流的高速性和无限性以及计算机资源的有限性使得提高数据处理速度成为数据流管理系统(DSMS)的关键;本文主要讨论了DSMS的核心技术———查询优化;着重研究了在shared-nothing机群并行系统中,通过并行查询处理技术来提高数据流处理速度的新方法.     

数据流处理技术

处理潜在无限的连续数据流的应用日益流行，传统数据库对快速变化的数据流进行在线分析的支持存在很多限制，需要对已存在的技术进行广泛的扩展研究，构建新的系统管理数据流．本文回顾近来数据流管理系统领域的相关工作和流项目的研究情况；分析了连续查询处理的新需求和挑战及数据流系统新颖之处．并提出在数据流研究方面的一些新看法。     

一种大规模流式数据聚类方法在交通热点分析中的应用

为了提高在大规模流式数据环境下交通热点区域分析的算法效率,提出了一种流式数据两阶段方法;该方法在第一阶段使用基于改进Canopy算法进行粗聚类并产生宏簇,在第二阶段使用K-means算法进行细聚类;并以粗聚类产生的宏簇个数和类簇中心位置为指导产生更加准确的微簇聚类结果。在试验中,使用流式数据两阶段方法对北京市出租车的定位数据进行了聚类分析;并结合热力图和电子地图对聚类结果进行可视化表达,在最终的热力分析结果中可以直观地发现出租车活动较为频繁的热点区域和线路,且与日常出行经验相符合。试验结果表明该算法能够实时地对流式数据进行聚类分析,产生的数据结果可供用户在任意时间窗口范围进行查询分析,有助于为交通活动情况实时分析、交通规划和拥堵治理等方面提供有价值的理论参考依据。     

一种基于层次聚类的流数据挖掘方法

流数据的特点在于数据流快速、有序地到达,并且数据海量,许多应用领域中生成的数据都可以归结为此类型．数据挖掘技术可以从海量的数据中发现有意义的知识模型,传统的数据挖掘算法通常是针对静态数据集,对流数据却无法有效地处理．文章试图从层次聚类角度处理流数据,并探讨了一种基于最小代价函数的层次聚类算法．     

数据库中字符型数据的加密及查询

加密是保护数据库中敏感信息的一种有效手段,如何在保证数据库安全的同时,实现对加密数据的高效查询是目前的一个难题。在此提出一个针对字符型数据的保存顺序加密方案,能直接在加密数据上执行字符串的等值查询;同时,通过构造索引字段储存字符串的结构信息,使子串查询时只需解密部分相关记录,较大地提高了子串查询性能。最后通过实验验证了加密系统的安全性与查询性能的提高。     

Query Translation on the Fly in Deep Web Integration

To facilitate users to access the desired information, many researches have dedicated to the Deep Web （i.e. Web databases） integration. We focus on query translation which is an important part of the Deep Web integration. Our aim is to construct automatically a set of constraints mapping rules so that the system can translate the query from the integrated interface to the Web database interfaces based on them. We construct a concept hierarchy for the attributes of the query interfaces, especially, store the synonyms and the types （e.g. Number, Text, etc.） for every concept At the same time, we construct the data hierarchies for some concepts if necessary. Then we present an algorithm to generate the constraint mapping rules based on these hierarchies. The approach is suitable for the scalability of such application and can be extended easily from one domain to another for its domain independent feature. The results of experiment show its effectiveness and efficiency.     

支持复杂语义的数据流滑动窗口连接建模和查询优化

数据流连接操作的执行方式直接影响到查询执行的效率和结果的正确性.在STREAM项目流化方法的基础上,对复杂应用下的数据流滑动窗口连接的准确语义进行了分析和建模,以时间窗口连接的增量维护为例提出了两种改进的基本维护策略,给出了针对元组窗和分组窗的维护方法,讨论了根据参数和环境的不同进行适应性的维护.实验证明了在不同的窗口、流速和选择度下,适应性地选择不同的优化算法会达到最优的处理性能.     

基于流数据的动态存储技术

对比了传统的数据与流数据的存储方法，并总结了现有流数据存储方式的优缺点，在继承了双向流的优点基础上，针对多数据源、多查询及多级存储建立了一个新的流数据处理系统模型，给出了解决历史数据存储的几种方案，更加突出了“实时性与历史性结合”的特点，同时满足了历史数据查询的需要，实现了流数据的动态存储策略。