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

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

Fast Nearest-Neighbor Query Processing in Moving-Object Databases

A desirable feature in spatio-temporal databases is the ability to answer future queries, based on the current data characteristics (reference position and velocity vector). Given a moving query and a set of moving objects, a future query asks for the set of objects that satisfy the query in a given time interval. The difficulty in such a case is that both the query and the data objects change positions continuously, and therefore we can not rely on a given fixed reference position to determine the answer. Existing techniques are either based on sampling, or on repetitive application of time-parameterized queries in order to provide the answer. In this paper we develop an efficient method in order to process nearest-neighbor queries in moving-object databases. The basic advantage of the proposed approach is that only one query is issued per time interval. The time-parameterized R-tree structure is used to index the moving objects. An extensive performance evaluation, based on CPU and I/O time, shows that significant improvements are achieved compared to existing techniques.     

数据流上的连续预测聚集查询

提出了一种数据流上未来值的连续查询,称为连续预测查询．采用数理统计的方法给出了带有COUNT聚集函数的连续预测聚集查询实现算法．通过采用TPC-H标准测试数据和随机生成的模拟数据进行了实验．理论和实验结果表明,给出的带有COUNT的连续预测聚集查询实现算法具有很高的性能和精度．     

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

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

空间文本数据流上连续查询评估技术综述

空间文本数据流上连续查询(CQST)在基于位置的服务中应用广泛,其在不断更新的数据流上,持续监控满足空间和文本约束的结果.为了将数据流中的对象尽快匹配给CQST,在CQST上构建高效的过滤技术是关键.CQST查询评估方法——为查询选取恰当的空间文本索引,构建高效的过滤策略提升索引的空间文本过滤性能,为数据流中到来的对象...     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

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

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

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

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

数据流查询处理中一种共享的分级窗口维护策略

由于数据流具有无界的特性,数据流系统中的查询多为带有窗口的查询,对带有窗口的查询,现有方法常由操作符直接维护窗口,但操作符的类型及排列方式可能会导致窗口难以维护,且冗余度较大.因此提出一种查询处理中的分级窗口维护策略,将窗口分为流窗口和操作符窗口,以流窗口为主并控制操作符窗口的维护,使查询中的窗口保持一致,解决了窗口维护问题,并且符合流查询语言的语义,各级窗口中的数据通过共享来解决内存消耗问题.     

数据流上Ad Hoc查询的自适应处理算法

对数据流上的Ad Hoc查询进行自适应处理,需要保证已有查询计划快速在线更新和迁移,但现有方法实现新旧查询计划的更新需要大量的滑动窗口状态转换。为此,提出一种Ad Hoc查询自适应处理算法。该算法基于数据流概要分布特性和自定义评分模型,快速计算出现有查询计划的最佳增量更新,以实现新到达的 Ad Hoc 查询处理,降低新旧查询计划切换时间。在数据流benchmark Linear Road提供的高速公路数据集上进行实验,结果表明,与MS、PT方法相比,该算法可较快完成新旧查询计划的切换。     

基于网格的数据流连续约束Skyline处理技术研究

作为数据流上的一种重要查询,skyline对于很多在线应用都非常重要,包括移动运算环境、网络监控、传感器网络、股票交易等。与大多数数据流skyline处理技术不同,本文着重于约束skyline的处理。约束skyline支持用户定义在某些属性上的偏好,系统中存在多个约束skyline查询,为skyline查询处理技术带来了新的挑战。为了在高速数据流上对约束skyline进行高效处理,本文使用了一种网格索引存储元组,并提出两个算法用于计算和维护skyline集合,我们还为每个查询定义了影响区域,以减少在新元组到达和旧元组失效时需要处理的网格数目。理论分析和实验证明了该方法的有效性。     

一种XML数据流之上持续查询执行器的增量维护方法

在XML数据流的海量持续查询处理领域中,很少有研究涉及到在查询集合发生变化的情况下,如何调整查询执行器以满足当前查询集合的问题．由于XML数据查询的数目是海量的,查询执行器重新构建的代价非常高．针对上述问题,提出了基于转换累计自动机的查询执行器的增量维护方法,来完成查询集合的增量增加和删除,从而避免了执行器重构的昂贵代价．同时,利用XML文档DTD结构约束,提高了查询执行器增量维护的效率,减少了增量维护所导致的空间冗余．实验表明,该方法能够以有限空间为代价,有效完成XML数据流持续查询执行器的动态维护．     

基于层次组织位置数据库的连续位置相关查询处理

1 引言现有的数据库系统一般假设数据在未被显式修改前是不变的,例如:如果字段salary的值是30.000,那么只有通过事务更新才会改变该字段的值。但对连续变化的对象,如移动对象的位置,应用传统的数据库管理系统来管理会造成两种结果:或者移动对象位置的频繁更新占用大量的系统资源;或者使用移动对象过时的位置信息而导致错误的决策。     

更新数据流上的连续Skyline计算

本文考虑＂更新数据流＂场景下的连续Skyline计算问题。在该环境下,数据不再满足＂先进先出＂特性,使得传统基于滑动窗口数据流上的连续Skyline计算方法不再适用。在对问题进行了形式化描述后,本文提出了基本算法BUSM,在分析其不足的基础上提出了一种网格索引数据结构,基于该结构提出了GUSM算法。该算法利用了更新数据流中删除和添加操作成对同时出现的特性,以网格为单位表示影响区域并进行快速排除预处理。理论分析和实验结果证明了上述方法在更新数据流上连续计算Skyline的有效性。     

基于小波方法的数据流查询计算研究与应用

许多领域中大量应用所产生的数据流的处理已成为聚集数据处理的一个重要方面。文章在对数据流查询计算进行深入研究的基础上,分析了该情形下聚集查询语言与重写的特征,给出了一类有效的快速查询计算模型。该计算模型的核心是运用小波分析方法,通过建立有效的小波提纲来提高查询处理的效率。最后,在实际应用环境下对所给出的模型进行了应用分析。     

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.     

多数据流滑动窗口并发连接方法

提出一种多数据流滑动窗口连接方法M3Join及其实现架构Roujoin. Roujoin由一个连接路由表和多个连接区组成,其内容根据并发连接请求设置,先将新元组插入缓冲区,然后根据其路由标记查找连接路由表进入合适的连接区执行连接或输出给用户.如果产生连接元组,则更改其路由标记后送回连接路由表,并反复迭代直到没有连接元组.由于共享中间结果,在处理多个并发查询时只需扫描流元组一遍.实验结果表明M3Join具有良好的性能,能够满足并发连接查询处理的需求.     

不确定性Top-K 查询处理

高效Top-K查询处理在涉及大量数据交互的应用中是一项重要技术,随着应用中不确定性数据的大量涌现,不确定性数据的管理逐渐引起人们的重视.不确定性数据上Top-K查询从语义和处理上都呈现出与传统Top-K查询不同的特点.在主流不确定性数据模型和可能世界语义模型下,学者们已经提出了多种不确定性Top-K查询的语义和处理方法.介绍了当前不确定性Top-K查询的研究工作,并对其进行分类,讨论包括语义、排序标准、算法以及应用等方面的技术.最后提出不确定性Top-K查询面临的挑战和下一步的发展方向.     

无线传感器网络环境下时-空查询处理方法

在无线传感器网络环境中,观察者感兴趣的是由传感器网络监测得到的与时间-空间相关的事件,而不是传感器本身或者大量无关的观察数据.观察者会经常提出与事件相关的时-空查询,例如:“网络覆盖的某地理区域R中10:00~11:00发生了哪些事件?”.由于每个传感器节点只有有限的能量,因此,研究能量有效性的时-空查询处理算法成为一个重要的研究课题.给出了一种以数据为中心的时-空查询处理算法.针对3种不同的存储策略:以数据为中心的存储、外部存储和节点本地存储,分析比较了节点的能量消耗.系统地研究了在3种不同的数据存储策略下,事件发生的概率,节点密度,事件类型数目,查询数目,时-空查询地理区域的大小以及时-空查询时间窗口的大小对节点能量消耗的影响.理论与实验结果表明,在多数情况下,这种以数据为中心的时-空查询处理算法的能量消耗少于基于外部存储和本地存储的时-空查询处理算法.     

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.