一种分布式环境中的二分式多层网格skyline算法.pdfVIP

116 2013，49(18) ComputerEngineeringandApplications计算机工程与应用 一 种分布式环境中的二分式多层网格skyline算法 丁 日强 DING Riqiang 渤海大学 信息科学与技术学院，辽宁 锦州 121000 CollegeofInformationScienceandTechnology,BohaiUniversity,Jinzhou，Liaoning121000，China DING Riqiang．Dichotomousmulti-layergridmethodforskylinequeryindistributedcomputingenvironments．Computer EngineeringandApplications，2013，49(18)：116-119． Abstract：Inrecentyears，theskylinequeryhasreceivedmoreandmoreattention．Thisisbecauseofitsimportanceinmanyap— plicationsinvolvingdatabasevisualizationmulti-criteriadecisionmaking，dataminingandSOon．Mostofthepreviousworks haveputtheirattention on processing skylinequerieson centralized datasetswhich iscalledcentralized skylinequery,and manyresearchresultshavegot．However，thereality isthattherelateddatapractically scatteratseveraldifferentservers．The skylinequerycomputationneedstogatheralotofdatafrom theconnectedserversindistributedenvironment．Theexistingmeth— odsfordistributedskylinequery computationhavetwoproblems：firstly，theirprocessingtimeofraskylinequeryisslow；sec— ondly,theytransfermanyunnecessarydataamongserversinthenetwork．ThispaperproposesaDichotomousMulti—LayerGrid method(DMLG)．Theproposedmethodbasedonthegridmechanism usesthedichotomytominimizetheunnecessarytrans— ferreddata．Experimentsbasedondifferentdatasetsshow thatthisproposedmethodiSbetterthantheexistingmethods． Keywords：skylinequery ；distributedskylinequery；distributeddata；dichotomousmulti—layergrid 摘 要：skyline计算在数据挖掘、多标准决策和数据库可视化等领域有着非常重要的作用，这些年 已经得到了广泛的关 注 ，以往对于skyline查询的研究大多集中在处理集中的数据集上，即集中式skyline查询 ，已经得到 了很多的研究成果。然 而，实际情况是：相关数据几乎分散在几个不同的服务器上 ，因此在分布式环境中的skyline查询计算需要从各个服务器收 集大量的数据；现有的在分布式环境中的skyrline查询方法有两个主要 问题：一是skyline查询的处理时间较慢；二是在网络 中服务器之 间传输 了很多不必要的重叠数据。提 出了一种二分式多层 网格法(DMLG)，可以有效地处理在分布式环境中 的skyline查询。该方法利用网格 的方法，借鉴二分法，最大限度地减少 了不必要的重叠数据传输，基于不同的数据集的实 验表明，这种方法优于现有的方法。 关键词 ：skyline查询；分布式skyline查询；分布式的数据；二分式网格法 文献标志码 ：A 中图分类号：TP311 doi：10．3778d．issn．1002—8331．1203—0083 1 引言