基于四叉树的skyline查询算法

《基于四叉树的skyline查询算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、兰州大学硕士学位论文基于四叉树的Skyline查询算法姓名：盛莉珺申请学位级别：硕士专业：计算机软件与理论指导教师：马志新20090501兰州大学硕士研究生毕业论文摘要Skyline查询作为数据挖掘的重要分支，广泛应用于多标准决策、可视化和用户参考查询等领域。近年来，在数据库和信息检索研究领域，有效计算Skyline的问题已经引起国内外研究者的广泛关注。现有的技术主要是对数据实行批处理和在线处理，采用的划分方法主要为物理划分或根据分段的维值进行划分，并没有对被划分的各部分间所固有的特性进行深入分析。在本文中，我们首先分析了四叉树索引机制的结构特点，然后根据其特点

2、系统地提出了一种基于四叉树的新的Skyline查询方法—QBSQ算法。QBSQ算法利用四叉树的结构特性，动态的对数据集进行划分，并且在构造树的过程中删除被树中结点支配的数据点，同时还深入研究了划分后各区域间以及数据点之间的支配关系，通过分析可知某些区域之间不存在支配关系，由此可减少区域间及数据点之间不必要的支配检查。该算法由于实现了有效的过滤和减少了不具有支配关系的区域内数据点之间的支配检查，提高了执行效率。此外，还针对QBSQ算法在高维数据空间上存在的不足提出了一个改进算法QBSQ*，该改进算法利用低维空间划分高维空间的方法来解决高维空间Skyline查询问题

3、，节省了内存空间的占用，增加了高维空间Skyline查询的可行性。最后，在多个测试数据集上进行了实验验证，实验结果表明了QBSQ算法及其改进算法QBSQ*的正确性和有效性。关键词：数据挖掘，Skyline查询，四叉树，支配兰州大学硕士研究生毕业论文AbstractSkylinequery,asub-areaofdatamining,hasvariousapplicationssuchasmulti-criteriondecisionmaking，visualizationanduserpreferencequeries．Recently,indatabasean

4、dinformationretrieval，theproblemofhowtoefficientlycomputeSkylinehasattractedextensiveattention．CurrenttechnologiesSOfarmainlyfocusonbatchprocessingandonlineprocessingwhilethepartitionmethodsbasicallydependonphysicaldivisionorusedimensionalvaluesofsectionsandtheylackofin—depthanalysis

5、oftheintrinsicrelationsbetweentheregionspartitioned．Inthispaper'wedelveintotheconfigurationfeaturesofQuad-treeindexmechanismfirstly,andthensystematicallyexploreaQuad—treebasedalgorithmQBSQforcomputingskylinepointswhichcontributestoabetterperformancethantraditionalonesforskylinequerie

6、s．ThisalgorithmpartitionsdatapointsdynamicallybymeansoftheconfigurationcharactersofQuad-tree，andthendeletespointsdominatedbyother(s)whileconstructingthetree．Weanalyzethedominantrelationsbetweenpartitionedregionssimultaneously,andrealizethatsomeregionsdohavenon-domination．Byfiltration

7、andreductionoftheamountofworkfordominationcheckingbetweenthoseregions，ouralgorithmimprovesexecutionefficiency．Besides，weproposeallimprovedalgorithm—QBSQ木whichgiventhelackofQBSQinhigh-dimensionspace．ThealgorithmsolvesSkylinequeryprobleminhigh—dimensionspacebymeansofapartitionmethodfor

8、low—dimensio