论文摘要
数据流是连续、实时、有序的数据项序列。数据流广泛存在于因特网与传感器网络、交通与环境监控、工业控制、金融股市与电子商务交易等应用中。流数据挖掘与管理是近年来学术界和工业界所共同关注的问题。作为一种重要的数据挖掘技术,Skvline查询是近年来的研究热点。Skvline是定义在一个多维对象集上的集合,它由所有不被其它对象所支配的对象组成。Skyline对于数据挖掘可视化、用户偏好查询及多约束决策等问题具有重要意义。自从Skyline查询在学术界被提出以来,对该课题的研究迄今为止都非常活跃。数据流的特点是数据实时到达、规模宏大、次序独立以及数据往往只能一次读取。这就要求Skvline查询处理算法必需高效地处理数据流中到来的每一个对象,并且要求算法具有较低的时间复杂度。学术界已经出现了一些有关该课题的研究成果,但这些成果仅涉及数据流上全空间Skyline的查询处理,并且数据形式也仅限于集中式、确定性数据流。此外,现存算法没有很好地解决求影响时间与淘汰被新来对象所支配的对象这两个关键问题,导致算法性能较低。本文在对现有技术之不足进行了彻底改进的基础上,进一步解决了一些新的重要实际应用与需求。用户对数据对象各属性的关注往往是有差异的;实际应用中的数据流往往以分布式的形式出现,例如:金融股票交易、环境监测以及网络通讯等应用;最近两年以来,一种全新的被称为概率数据流的数据形态逐步引起了研究者们的关注,针对概率数据流的挖掘与分析方兴未艾。这些新的应用需求为数据流上的Skyline查询处理带了新的挑战。本文对数据流上的Skyline查询处理算法进行了系统地研究,主要成果概括为以下几个方面:(1).提出了一个高效地处理滑动窗口上Skyline持续查询的算法CridSky。对于数据流上的Skvline查询处理,决定其性能的主要因素是计算新到达对象的影响时间以及淘汰被新到达对象所支配的对象这两个关键过程的效率。对这两个关键过程,现有工作中只是简单地依靠R树上的窗口查询机制来实施,直接导致了算法性低下。GridSky算法采用更适合数据流这种频繁更新环境的基本网格作为索引结构,并在此基础上开发了基于时间戳的剪枝策略、基于网格的的剪枝策略以及分层遍历策略等优化措施,大幅度地提高了算法的性能。大量的对比实验表明,在空间复杂度略低的情况下,GridSky与其竞争对手相比时间性能优势在1个数量级以上。此外,GridSky算法对不同的数据分布、数据规模与维度具有很强的可扩展性。(2).研究了分布式数据流上的Skyline查询问题,提出了一个通信最优的分布式算法BOCS。近年来随着大规模分布式应用的涌现,分布式数据流上的查询处理与数据挖掘越来越引起了研究者们的关注。此前相关工作局限于集中式数据流上的Skyline计算,没有人考虑吏具挑战性的分布式数据流上的Skyline查询问题。本文围绕着降低系统反应延迟与最小化通信负荷的目标,在对GridSky进行重大适应性改造的基础上,提出了一个两阶段渐进求解的分布式算法BOCS。并对BOCS的关键实现环节,如:远程站点与协调站点间的通信协议、Skyline增量的计算等进行了优化,使算法达到了通信效率与反应延迟的合理均衡。理论分析证明在所有基于非共享策略的算法中,BOCS算法通信最优。大量的对比实验也表明,BOCS算法高效、稳定且具有良好的可扩展性。(3).提出了一个高效地计算滑动窗口中任意子空间上Skyline的算法StreamSubsky。此前相关工作仅限于维护滑动窗口全空间上的Skyline,未涉及到子空间上Skyline的计算问题。而用户的偏好与倾向性天然不同,这就催生了滑动窗口中子空间上的Skyline查询问题的研究。本文首次提出并较好地解决了该问题,提出的StreamSubsky算法巧妙地利用了全空间与各子空间上Skyline之间的关系,采用自顶向下的方式通过两个阶段增量地返回目标子空间上的计算结果。此外,算法还采用了多个优化策略显著地提高了计算效率。理论分析和实验结果表明,与同类算法相比StreamSubsky以极少的时间开销就能使查询得到响应,算法具有良好的时间与空间性能。(4).对概率数据流上的Skyline查询问题进行了深入研究,提出了一个高效的解决方案。数据的内在不确定性存信息集成、RFID以及传感器网络等普适计算环境中普遍存在。对概率数据流进行管理与分析近年来引起了研究者们的广泛关注,而此前尚无解决概率数据流上Skyline持续查询的算法出现。本文基于“可能世界”语义对该问题首次进行了建模,并提出了一个高效的查询处理算法SOPDS。与传统确定性数据流上的Skyline查询处理不同,SOPDS算法主要考虑以下两个基本问题:一是如何高效地确定对象的身份(判断其是否为Skyline对象),即减少身份判断过程中支配测试的次数以降低CPU开销;二是在保证算法正确性的前提下尽可能早地淘汰那些不再有机会加入Skyline的对象,以减少内存开销。围绕着以上两个基本问题,本文先后提出了概率定界、逐步求精、提前淘汰与选择补偿等优化措施对算法从时间与空间上进行了系统地优化。理论分析与详细的对比实验表明,SOPDS算法在时间与空间上具有较高的整体性能,算法高效、稳定。本文研究了数据流上Skyline查询的四个重要问题,并分别提出了有效的解决方案。本文提出GridSky算法对现有技术进行了彻底地改进,而提出的BOCS、StreamSubsky和SOPDS算法则进一步填补了一些重要新兴应用的空白。理论分析证明这些算法高效地解决了相应的问题;大量的对于比实验也表明,与现有技术相比本文提出的算法在存储空间、查询处理速度等方面具有明显的优势。