一种存储和索引历史数据流数据的方法*

通过对流数据的抽样存储,并在内存中建立B 树结构,对抽样数据和常用聚集操作进行索引,实现了对无限数据流历史数据的抽样存储管理,有效地支持了数据流历史数据查询.     

一种新的数据流在线压缩存储方法

针对当前数据流采用的抽样存储方法忽略了对数据流历史数据的分析处理与存储管理的问题,提出一种新的存储数据流的方法。在满足数据精度的情况下,采用加权最小二乘法对缓存数据流进行分段曲线拟合,对拟合结果进行聚类分析。根据聚类分析结果,采用合适的窗口对数据进行分段曲线拟合,利用拟合结果预测数据流的趋势。将预测结果与实际数据比较,根据比较结果采用不同的方法存储。实验结果表明,提出的方法具有良好的性能,能够满足不同的处理需求。     

数据流与磁盘存贮表的连接计算算法

数据流与存贮表的连接查询经常出现在主动式数据仓库的维护中,与传统的关系数据库的连接计算不同,数据流快速处理的要求不允许将数据流先存入磁盘再计算,而计算机内存无法存储无界增长的数据流,因此数据流查询采用先处理再存储结果的计算方式。数据流与存贮表的连接计算算法重点要解决内存开销和处理速率二个问题。MESHJOIN算法最早提出将存贮表划分为若干个数据块,将数据块交替放入内存与数据流窗口完成连接计算。在MESHJOIN算法思想的基础上将存贮表的内存数据块也划分为若干逻辑分区,每次连接计算仅替换其中的一个逻辑分区,有效地降低了数据流滑动窗口所需的I/O代价,从而提高滑动窗口的计算速率。最后通过实验对二种算法在内存开销和计算速率进行了比较。     

基于Multi-Bloom Filters的数据流聚集查询

针对数据流上任意时闯段的历史数据的聚集查询问题,提出基于BF技术的概要存储模型MBF。采用全局比特位向量提供数据元素的快速插入和查找,结合动态分配的局部计数器向量存储不同时间段下的历史数据,使MBF支持不同时间粒度上历史数据的有效存储和高效查询,给出历史时间跨度较大情况下MBF的压缩方法以及MBF模型的参数最优化设置。理论分析证明,MBF具有较大的灵活性,能有效支持时间范围内历史数据元素的近似聚集查询。     

基于BD结构的历史数据流存储与查询

实际应用中,人们往往不仅需要近期数据流,还需要结合大量历史数据流来共同解决问题。研究表明,处理大量历史数据流时,传统数据库索引技术(如B+树)不能提供高的存储利用率和查询效率。针对任意时间段历史数据流的存储查询问题,提出一种基于BD结构的存储与查询方法。该方法将BDTree和BDHash相结合,能有效降低BDTree的高度,减小索引项的规模,同时可以避免数据结点规模过大。在此基础上,研究了部分扩充策略以解决数据插入失败问题。理论分析和实验结果表明,该方法能提高存储空间利用率和查询效率,可以有效应用于历史数据流的存储和查询。     

面向轨迹流数据的索引构建与存储方法研究

移动社交网络等基于定位服务应用的快速发展导致时空数据流规模呈爆炸式增长,要求底层数据存储系统支持高吞吐量轨迹数据的插入以及空间和时间约束下的低延迟查询,而现有HBase等数据存储方案因索引更新开销过高无法满足该需求。针对时空数据流的应用特性,提出一种数据流内存索引及存储方法。根据键值和时间范围对历史与增量数据元组进行物理分区,将其以模板B+树的形式写入内存并构建索引以增强快速写入和查询能力,同时对数据进行压缩存储提升索引效率。在此基础上,采用多级索引根据数据分区将复杂查询分解为可独立处理的子查询。实验结果表明,与传统HBase、WaterWheel等方法相比,该方法在不同数据插入和查询条件下的数据存储性能与查询效率更优。     

大数据分析下分布式数据流处理技术研究

由于数据流的不稳定性,将数据流查询安排在固定节点上就会造成分布式数据流处理技术很难对计算资源实现较高的处理效率,基于此,提出大数据分析下分布式数据流处理技术研究。具体流程是数据收集、历史数据的存储和查询、Storm实时处理、智能索引、数据模型的建立。根据实验结果可知,本文提出的大数据分析下分布式数据流处理技术与传统技术相比,在数据流的处理效率上占有较大优势,一般维持在75%以上,能够大大节省处理时间。     

数据流上的预测聚集查询处理算法

实时数据流未来趋势的预测具有重要的实际应用意义.例如,在环境监测传感器网络中,通过对感知数据流进行预测聚集查询,观察者可以预测网络覆盖的区域在未来一段时间内的平均温度和湿度,以确定是否会发生异常事件.目前的研究工作多数集中在数据流上当前数据的查询,数据流上预测查询的研究工作还很少.采用多元线性回归方法,给出了数据流上的聚集值预测模型,提出了一种数据流预测聚集查询处理方法.当预测失败的次数大于预先给定的阈值时,给出了一种预测模型自动调整策略,以降低预测误差.还提出了滑动窗口的更新周期、数据流的流速对预测精度影响的数学模型.理论分析与实验结果表明,提出的预测聚集查询处理算法具有较高的性能,并且能够返回满足用户精度要求的预测查询结果.在实验中,采用TPC-H国际标准测试数据和TAO(tropical atmosphere ocean)测量的海洋表面空气温度数据来构造数据流.     

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

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

StreamQCTree:一种流数据方压缩结构

数据流管理系统计算聚集查询结果保存在内存中形成流数据方(StreamCube),提供快速、精确的在线OLAP查询。有限的内存空间需要一种有效的存储方法来存储更大时间窗口的流数据方。提出一种基于QC-Tree结构的流数据方StreamQCTree生成、裁剪及查询方法。将QC-Tree结构中上界集划分为基本上界类和附加上界类;并分析附加上界类的成本计算模型;根据该模型在固定存储空间下,采用动态选择物化结点的方案选择物化部分附加上界类,使对StreamQCTree的平均查询响应时间最小。实验表明,StreamQCTree能够有效地访问数据方且获得较好的压缩效果。     

流数据分析与管理综述

有关流数据分析与管理的研究是目前国际数据库研究领域的一个热点.在过去30多年中,尽管传统数据库技术发展迅速且得到了广泛应用,但是它不能够处理在诸如网络路由、传感器网络、股票分析等应用中所生成的一种新型数据,即流数据.流数据的特点是数据持续到达,且速度快、规模宏大;其研究核心是设计高效的单遍数据集扫描算法,在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构--概要数据结构,使得在任何时候都能够根据这个结构迅速获得近似查询结果.综述国际上关于流数据的概要数据结构生成与维护的研究成果,并通过列举解决流数据上两个重要问题的各种方案来比较各种算法的特点以及优劣.     

ArchDB:一个高可靠高性能海量归档流数据库

当前,在科学实验、网站安全、内网审计等诸多领域,监视在线事务或跟踪用户行为会产生大规模归档流数据.这些归档系统规模可达PB级(10~(15)B).在如此规模下存储和分析这些结构化数据至少带来3个挑战;1)数据可靠性问题;2)高效存储和分析高速持续的流数据问题;3)高性能和高可靠目标之间的冲突问题.在分析归档流数据特征的基础上,提出了一种新的高可靠数据库体系结构ArchDB.ArchDB由两部分组成:其一负责加载和查询较小规模的当前数据;其二负责存储和查询大规模的历史归档数据.通过优化设计ArchDB中的数据分布策略、数据块尺寸和归档时机、数据存储和归档流水化机制来高效可靠管理大规模数据.实验结果表明ArchDB既能加倍数据加栽性能,又能加速恢复过程,其加速效果取决于恢复并发度.     

基于自动机的XML流多查询处理

XML流数据处理在研究领域引起广泛关注,该文针对XML流上的多查询处理提出一种算法,把多个查询合并为一个共享前缀的查询树,应用自动机和运行时栈相结合的方法,单遍扫描XML流处理数据流上的多个查询。该算法采用一种分层栈结构保存查询模式匹配候选集,利用XML节点的区间编码来确定节点之间的关系,返回整条匹配路径。     

数据流中基于滑动窗口的最大频繁项集挖掘算法*

挖掘数据流中最大频繁项集是从数据流中获得信息的一种有效手段,是数据流挖掘研究的热点之一。结合数据流的特点,提出了一种新的基于滑动窗口的最大频繁项集挖掘算法。该算法用位图来存储数据流中流动的数据;采用直接覆盖的方法存储和更新数据流上的数据;在深度优先搜索挖掘最大频繁项集时,除采用经典的剪枝策略外,还提出了与父等价原理相对应的子等价剪枝策略;最后将挖掘结果存储在索引链表中以提高超集检测效率,进一步减少挖掘最大频繁项集的时间。理论分析和实验结果证实了该算法在时间和空间上的有效性。     

界标窗口中数据流频繁模式挖掘算法研究

数据流的流量太大会无法被整个存储,或被多次扫描。为此,在研究已有挖掘算法的基础上,提出一种界标窗口中数据流频繁模式挖掘算法DSMFP_LW。利用扩展前缀模式树存储全局临界频繁模式,实现单遍扫描数据流和数据增量更新。实验结果表明,与Lossy Counting算法相比,DSMFP_LW算法具有更好的时空效率。     

基于流数据技术的信息监测系统的研究与设计

以开发的网上信息监测系统为应用背景，建立了流数据应用的原型系统。通过Internet互联网实现网络数据截获、监控、还原、查询及存储等技术，提出并应用了连续查询及动态存储策略，在原型系统中测试了系统的性能。     

基于Storm的流数据KNN分类算法的研究与实现

KNN算法是一种简单、有效且易于实现的分类算法,可用于类域较大的分类。近年来对KNN算法的研究偏向于静态大数据集,不过,在越来越多的情况下要用KNN算法在线实时处理流数据。考虑到流式数据流量大,连续且快速,不易存储和恢复等特性,以及流处理系统Storm对流数据处理具有实时性、可靠性的特点,提出了基于Storm的流数据KNN分类算法,该算法首先对整个样本集进行划分,形成多个片集,然后计算出待分类向量在各片集上的[K]近邻,最后再将所有片集[K]近邻归约得出整体[K]近邻,实现待分类向量的分类。实验结果表明,基于Storm的流数据KNN分类算法能够满足大数据背景下对流数据分类的高吞吐量、可扩展性、实时性和准确性的要求。     

Online wavelet-based density estimation for non-stationary streaming data

There has been an important emergence of applications in which data arrives in an online time-varying fashion (e.g. computer network traffic, sensor data, web searches, ATM transactions) and it is not feasible to exchange or to store all the arriving data in traditional database systems to operate on it. For this kind of applications, as it is for traditional static database schemes, density estimation is a fundamental block for data analysis. A novel online approach for probability density estimation based on wavelet bases suitable for applications involving rapidly changing streaming data is presented. The proposed approach is based on a recursive formulation of the wavelet-based orthogonal estimator using a sliding window and includes an optimised procedure for reevaluating only relevant scaling and wavelet functions each time new data items arrive. The algorithm is tested and compared using both simulated and real world data.