论文部分内容阅读
近年来，随着互联网、云计算等技术的发展，人类社会所产生的数据正以前所未有的速度在不断的增长和累积，我们已经步入大数据时代。研究大数据的意义在于从数据中发掘重要信息，为人类的生产、生活创造价值。如何从海量数据中高效、准确的提取出所需要的信息是当前的研究热点。 Skyline查询作为一种从数据集中发现有价值信息的重要方法，近几年受到研究人员的极大关注，有关skyline查询的研究取得了长足进步。Skyline查询在无线传器网络、基于地理位置的服务及基于Qos的网络服务选择等实际场景中得到应用，且发挥了举足轻重的作用。然而，随着待处理数据量的不断增加及数据来源的多样化，skyline查询的计算性能及适用范围面临严峻挑战。本文以静态数据集上的skyline查询为切入点，旨在研究更为高效的skyline计算方法，以应对海量、高维、多来源数据所带来的挑战。本文的主要研究内容及贡献具体包括: (1)开展反相关数据集上skyline算法的研究，提出一个高效的skyline查询算法RSAC。单个数据集上的skyline查询算法是skyline问题的研究基础，也是skyline领域中研究最为深入的问题。然而，在反相关数据集上，skyline查询算法运行效率低这一问题始终未得到很好的解决。且在大数据集上，这个问题将变得更加严重。本文针对这一问题展开研究，文中首先定义了反相关系数，用以定量描述数据集的反相关分布程度。然后提出了一个具有简洁计算流程的反相关数据集skyline算法RSAC。该算法将传统算法计算过程中所使用的两个计算阶段（determination与elimination）进行紧密融合，巧妙的使用一个索引结构(kd-tree)实现加速两个阶段计算的目的。该算法通过将支配比较转化为kd-tree上范围查询的方法，实现对候选向量是否为skyline点的快速判断，由此降低大量计算开销，极大的加速了计算过程。此外，本文对算法提出了三种优化方法。即结点插入优化、边界矩形优化，以及动态维护树平衡优化。三种优化方法都不同程度的提升了算法的性能。实验表明，RSAC比目前最优的反相关数据集skyline算法SOAD快2-4倍。 (2)开展skyline join结果集基数估算研究，提出skyline基数估计算法GrouD。Skylinejoin结果集基数估计是skyline join查询优化的基础，具有重要的研究意义。然而，此问题目前尚未得到研究，本文成为首个对此问题进行研究的工作。文中基于已有的分组方法，提出了skyline join估算方法GrouD。GrouD首先两个表进行分组预处理，将每个表按连接属性进行分组，根据元组在组内及各组间的支配关系将每个数据集各划分为LSS和LSN两个分片。通过已经证明的定理可知，除LSN(＞＜)LSN外，由其它三种连接组合LSS(＞＜)LSS、LSS(＞＜)LSN及LSN(＞＜)LSS所生成的元组一定为连接结果集中的skyline点。这三种连接组合产生的元组数量可根据每个表上连接属性的分布频率求得。而由LSN(＞＜)LSN生成的元组中所包含的全局skyline点数量则通过抽样方法进行测算。由此可以得到两个表的skyline join结果集基数估算值。 (3)开展关于skyline join查询的研究，提出了适用于两个及两个以上表的skylinejoin查询算法Skyjog。连接操作的特性决定skyline join查询面临着中间结果集大、数据维数迅速增加等挑战。且skyline join结果集无法直接通过每个数据集的skyline结果直接得到。在计算两个表的skyline join查询结果时，本文使用分组方法对每个表进行分组预处理。由于LNN分片对产生最终结果没有贡献，因将其去除。最终，每个表被划分为LSS和LSN两个分片，可以得到四个连接组合。由文中已经证明的定理可以保证其中三个连接组合所生成的元素一定在最终的skyline join结果集中，因而仅需对余下的一种连接组合所生成的元素做进一步的判断，即可得到最终的结果集。此外，经过适当调整，将分组方法扩展至多于两个表的情况。据此，提出了可用于两个及更多表上的skyline join查询算法Skyjog。大量的实验表明，与当前最优的算法相比，Skyjog算法具有最高达上百倍的性能的提升。