top-k潜力skyline查询的研究

《top-k潜力skyline查询的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文Top-K潜力Skyline查询的研究姓名：方仲康申请学位级别：硕士专业：计算机软件与理论指导教师：刘玉葆20100602Top-K潜力Skyline查询的研究论文题目：Top．K潜力Skyline查询的研究专业：计算机软件与理论硕士生：方仲康指导教师：刘玉葆副教授摘要Skyline查询是找出一个多维集合中所有不被其它点支配的数据点集，它在实际应用中主要用于多维决策支持。如在只有价格和离海边距离两个属性的酒店集合中，旅客通过Skyline查询会找出其中的Skyline酒店，它们在这两个属性上不比别的酒店差并且至少在某个属性上要优于其它酒店。Skyline查询

2、可以很好地找到满足用户要求的那些点，但是它不支持找出其它有潜力成为满足用户要求的点，如酒店投资商就希望从那些非Skyline酒店中找出一些有潜力发展成为Skyline酒店的点做为投资对象，因为这些点可以让他们的投资带来更大的回报。基于这样的实际需求，本文提出了Top．k潜力Skyline查询问题，用于查找多维集合中七个最有潜力成为Skyline的非Skyline点。本文给出了问题的形式化定义，并提出了两种基于数据网格的求解算法和相关的剪枝策略。Grid．E算法是第一个算法，它的主要思想是迭代遍历数据网格的交点；第二个算法Grid．P采用了递归的集合划分和空间投影方法来求解问题，

3、针对该算法本文给出了它的正确性证明。在本文的最后，我们在真实数据和合成数据集上对这两个算法进行了详细的实验测试，实验结果说明了算法的有效性。关键词：Skyline、潜力Skyline、临界点、关键临界点、临界代价、最小临界代价Top-K潜力Skyline查询的研究AbstractTitle：Major：Name：Supervisor：FindingTop-KPotentialSkylinesComputerSoftwareandTheoryZhongkangFangYubaoLiuAbstractGivenamulti—dimensionsetD，Skylineistheset

4、ofpointswhichares’tdominatedbyothersinD．It’Smainlyusedformulti-critieriadecision,forexample，skylinequeryCanfindtheskylinehotelsthatnootherhotelscanbebetterthanthemonallattributes，anduserscanjustchooseoneofthesehotels．Skylinequerycallfindthebestpointsthatusresprefer,butitCan’tfindthepotential

5、points．Forexample，ahotelinvestormaywanttofindsuchnon-skylinehotelsthathavethepotentialtobeskylinehotels，becausetheyCanbringhimmoreprofits．Inthispaper,weproposeanew1【indofTop-Kpotentialskylinequery,whichCanfindthemostpotentialkpointstobeskyline．We酉Veoutthedefinitionoftheproblem,andproposedtwo

6、aloeo-ihtmsbasedOildate酣d．Grid-Eisthefirstalgorithmaccordingtosearchallthegridintersectionpointstohandletheproblem．AlgorithmGrid—Pusessetdividingandspaceprojectiontohandleit．Moreover,weprovethatOUralgorithmscanfindtheoptimizationqueryresults．Theexperimentalresultsbasedonrealdatasetsandsynthe

7、sizedatesetshowtheefficiencyandeffectivenessofouralgorithms．KeyWords：Skyline，PotentialSkyline，CriticalPoint,KeyCriticalPoint,CriticalCost,MinimalCriticalCoStⅡ论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成