论文部分内容阅读
不确定数据流作为一种特殊的数据流类型,广泛存在于环境监测、基于位置的服务、金融股市交易以及Web信息系统等众多实际应用中,对不确定数据流进行高效查询分析已成为当前大数据研究的一个重要研究领域。不确定数据流的Skyline查询作为不确定数据流分析的一个重要方面,在金融领域、互联网领域以及无线传感器网络等众多实际应用中发挥着重大作用,目前已成为大数据领域的一个研究热点。当前不确定数据流Skyline查询存在的主要挑战在于:一方面,由于现实应用中的不确定流数据往往源源不断高速到达,导致传统集中式查询处理方法难以满足高速增长的查询计算需求,迫切需要研究并行查询处理方法;另一方面,随着用户查询需求的多样性变化,使得传统Skyline查询定义在实用性方面存在不足,迫切需要研究新型查询定义下的查询处理方法。以上研究挑战表明,不确定数据流的并行Skyline查询技术研究具有极其重要的现实意义,且已成为当前Skyline查询分析技术研究的必然趋势。当前高性能计算以及云计算等计算环境的发展和普遍运用,为实现不确定数据流的并行Skyline查询处理提供了强有力的并行处理能力,而n-of-N Skyline查询和k-支配Skyline查询等新型Skyline查询定义,能够有效地解决查询实用性不足的问题。因此,本文围绕上述两个方面的研究挑战,分别针对不确定数据流的并行n-of-N Skyline查询技术和不确定数据流的并行k-支配Skyline查询技术开展研究工作。针对已有查询方法因难以同时支持多个不同尺寸窗口查询而导致实用性不足且查询效率不高的问题,提出了一种基于区间树刺探的并行n-of-N Skyline查询方法PnNS。在PnNS方法中,首先利用一种滑动窗口划分策略将全局滑动窗口划分为多个局部窗口,从而将不确定数据流的集中式查询处理过程并行化。其次,通过一种查询区间编码策略将不确定数据流的n-of-N Skyline查询转化为刺探查询,从而提高查询的效率。同时,为进一步优化查询处理的过程,一方面通过一种流数据映射策略将最新到达的流数据元组映射至相应的局部窗口,以最大程度实现各计算节点上的负载均衡;一方面基于空间索引结构R树组织不确定流数据,以减少流数据之间支配关系的测试开销。实验结果表明,和已有方法相比,PnNS方法在保证查询结果正确性的基础上,有效地提高了查询处理的灵活性和效率。针对已有查询方法因查询结果集合过大而导致实用性不足且查询效率不高的问题,提出了一种基于支配能力索引的并行k-支配Skyline查询方法PKDS。在PKDS方法中,首先定义了不确定数据流的k-支配Skyline查询问题。其次,基于窗口划分的流数据映射策略,将最新到达的流数据元组映射至计算节点,有效地实现了不确定数据流的k-支配Skyline查询的并行化。特别地,采用基于流数据元组k-支配能力的索引结构对流数据元组进行高效组织管理,极大地提高了滑动窗口中流数据元组之间的k-支配关系测试效率。实验结果表明,PKDS方法能够将高维数据的Skyline查询结果缩小至具有更好决策支持的范围,并且在保证查询结果正确性的基础上,极大地提高了查询处理效率。