skyline性质及算法分析word论文.docxVIP

Skyline 性质及算法研究摘要随着大数据时代的到来，数据存储和数据查找越来越困难，那么如何在 海量数据中快速找到所需的数据自然是人们研究的热点和难点。Skyline 查 询 就 是 一 种 重 要 的 查 找 数 据 的 方 法 ， 是 数 据 挖 掘 的 主 要 分 支 之 一 。 Skyline 是不被其他点所支配的全部点的集合。本文对 Skyline 查询进行了深入的研究。取得了如下的结果：1. 给出了 Skyline 的性质。2. 对 PR 四叉树的结构作了深入细致的分析，在此基础上给出了基于 PR 四叉树的 Skyline 查询算法。基于 PR 四叉树的 Skyline 查询算法主要是 根据 PR 四叉树的结构特点，即象限间的支配关系来查找 Skyline，在建树 的过程中就剪枝掉了部分数据，提升了计算 Skyline 的效率。3. 对 MB-树的性质进行了深入的研究，给出了基于 MB-树的 Skyline 查询的剪枝规则，从而给出了查询算法。该算法利用 MB-树的序的关系来 划分数据，得到包含数据的 MBR，利用 MBR 和 MBR 之间的支配关系来剪 枝 MBR，降低数据量，提高算法的计算效率。4. 通过实验分析证明了两个查询算法的正确性和有效性。关键词Skyline Query；支配；PR 四叉树；MB-树；MBRResearch on the Properties and Algorithms of SkylineAbstractWith the arrival of the era of big data, data storage and data search become more and more difficult, so how to quickly find the required data from the massive data is the hot and difficult point of people’s research naturely. Skyline query is a kind of important data searching, and one of the main branches of data mining. Skyline is the set of all points that are not dominated by other points.This paper makes an intensive research on Skyline query. The results are as follows:Some properties of Skyline were given.A deep and detailed analysis was done on PR-quadtree’s structure, based on it this paper gives the Skyline algorithm based on the PR-Quadtree. The Skyline algorithm based on the PR-Quadtree is mainly according to the structure characteristics of the PR-quadtree, namely the dominance relation between the four quadrants to find the Skyline, with the building process, a lot of the data are pruned away, and the computation efficiency of Skyline is improved.A deep analysis of MB-tree’s character was made, and then the pruning rules of the Skyline query based on MB-tree were given, thus the query algorithm was given. This algorithm divides the data by the order of MB-tree. To get the MBR contained datas, using the dominance relation between the MBR to prune MBR, to reduce the amount of data, to improve the computation efficie