数据流上连续动态skyline查询研究

skyline查询能够从大规模数据集上计算满足多个标准的最优点.数据流上的skyline计算是数据流上最基本的查询操作之一,对于很多在线应用具有非常重要的意义,尤其在移动计算环境、网络监控、通信网络以及传感器网络等领域.不同于大部分传统的skyline研究,主要研究数据流上约束skvline和动态skyline计算问题.采用网格索引存储元组,提出了GBDS算法用于计算和维护动态skvline.通过为每个查询定义影响区域,使得在元组到达和失效时需要处理的元组个数最小化.理论分析和实验结果证明了提出方法的有效性.     

一种大规模分布式监控系统中预测模型的研究

大规模分布式监控系统面临着数据管理规模和资源约束之间的矛盾,通过预测模型方法可以有效降低网络通信开销.在定义描述问题域和分析相关工作基础上,提出了两个改进的预测模型,并给出了当预测失败时对应的调整策略.采用了模拟数据和TAO(tropical atmosphere ocean)测量的海洋表面空气真实温度数据作为实验数据流,对改进模型进行了实验.理论分析和实验结果均表明,改进后的模型具有更高的预测命中率和更低的网络通信开销.     

滑动窗口数据流上多极值查询资源共享策略研究

为了提高在同一数据流上同时计算多个连续极值查询(MAX或MIN)时的处理能力,对查询间资源共享技术进行了研究.提出了一种称为"关键点集"的裁剪策略,系统仅需保存少量数据即可满足所有查询的需要.发掘多个查询间的相似性和可共享的计算存储资源,提出了一个多极值查询处理算法MCEQP.采用链表结构实现的该算法,当一个新数据到达时最多需要O(M K)时间即可更新全部K个查询的结果,其中M为关键点集包含数据的个数.MCEQP采用触发器驱动的方式,只在某些特定时刻才需要计算因数据失效引起的查询结果变化,更新K个查询结果所需时间为O(K).理论分析和实验证明,对于滑动窗口数据流上的多个极值查询,MCEQP算法在降低存储开销和提高性能方面均优于现有的通用方法.     

即时消息交换系统服务器设计与实现

即时消息传递(IM——Instant messaging)是Internet上日渐普及的一种通信方法。当前有许多被使用的IM协议，但它们之间的互通性比较差。为了推动IM的进一步发展，提出了一个针对企业级应用的即时消息交换系统模型，介绍了模型所用的通信协议，并详细讨论了消息服务器的设计和在Windows平台上的具体实现。通过理论分析和实际应用，证明了所做的研究是可行的。     

大规模分布式系统中低通信阈值监控方法

为了进一步降低分布式阈值监控处理中的通信开销,把多个被监控对象作为整体进行统一处理,充分利用对象间的相对关系,提出了一种比分别单独监控更加有效的方法CEM（Communication Efficient Method）。该方法在所有未超过阈值的对象中选择具有最大全局值的对象作为代表,通过调整因子使得代表对象调整后的局部值在每个节点上看来都是最大,因此只需对代表对象进行持续监控即可保证正确性;将多个对象的持续监控变为对代表对象的监控和对局部约束条件的维护操作,当局部约束被打破时,才需要通信并进行参数调整以重建约束。真实数据集上的实验表明,CEM方法能够有效降低分布式阈值监控中的通信开销。     

基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.