论文部分内容阅读
数据本身存在不确定性、采集的随机性及不精确性,如在地质测量、天文观测、气象、传感网络、移动对象搜索和数据集成等实际应用中,由于复杂的外界因素的影响使得采集到的数据不确定、不完整和不精确。对这些不确定的海量数据集进行挖掘时,常规的方法是通过数据清洗、集成等预处理后再进行挖掘。然而,经过加工后的数据通常丢失了大量的原始信息,从而导致挖掘效果难于满足需求。近年来,出现了一种新型数据集-不确定数据集,即将源数据中的不确定性用概率(或置信度)表达。不确定数据集上的数据挖掘也随之成为近年来的研究热点。其中不确定数据集上的Skyline挖掘是一个重要的研究领域。尽管Skyline挖掘获得了广泛的研究,但由于现有的方法没有将数据集的不确定性考虑到计算模型中,因而无法实现在该类数据集上进行Skyline挖掘。经过广泛细致的研究工作后,本文提出了有效的方法来解决该类问题。通过对现有的不确定数据集上Skyline及Top-k查询算法的研究,结合了数据流的特性,本文提出了全新的用于不确定数据集上的一系列Skyline查询维护算法,并基于真实数据及合成数据进行了大量的实验验证,试验结果表明本文设计的算法能高效且有效地在不确定数据集上进行Skyline挖掘。本文的主要研究成果如下:1)针对稀疏实例分布数据集,提出了基于多维网格索引的GIKS(Grid indexedk-Skyline)算法。该算法的核心思想是利用网格索引进行自底向上的最优化访问,即把数据空间分割为多个易于处理的小区域,利用网格的优势分而治之,从而快速地响应用户发出的查询请求。GIKS算法还使用了IDM(InstancesDistribution Map)检索结构在空间遍历过程中实现信息共享,大幅降低时间复杂度。2)针对密集实例分布数据集,提出了基于分层树索引的BRKS方法。当在实例密度很大的数据集上进行k-Skvline查询时,本文又提出了一种自顶向下的BRKS(Bounding and Refining k-Skyline)方法,它以均值评估为基础,利用分层树进行限界求精,从而渐进地计算对象的Skyline概率。3)将不确定数据集扩展到数据流上,提出了概率数据流的Skyline查询维护方法。对概率数据流上的Skyline查询问题进行了深入研究,并基于“可能世界”语义对概率数据流上的Skyline查询计算问题首次进行了建模。4)针对概率数据流上的skyline查询处理,本文设计了一种高效的查询处理算法SKY-PDS(Skyline over Probabilistic Data Stream)。与确定型数据流上的skyline查询处理不同,SKY-PDS算法主要涉及到两个基本问题:①如何驹绲靥蕴切┎辉儆谢峒尤隨kyline结果集的对象,以减少内存开销?②如何高效地判定对象的状态(是否作为Skyline对象输出),即如何减少对“支配关系”的检测次数以便降低CPU负荷?针对以上两个基本问题,本文先后提出了概率定界、逐步求精等优化措施对算法从空间与时间上进行了系统地优化。缜密的理论分析和详尽的实验对比表明,SKY-PDS算法在空间与时间上都具有较高的性能,且算法具备良好的扩展性。5)对于本文设计的多个算法均进行了详尽的试验验证,试验数据来源于两方面:真实NBA数据以及通过标准数据生成算法产生的不同分布特性的数据集:独立分布、相关分布及反相关分布数据集。对于每组试验结果都进行了详细的分析。