ParallelComputationofSkylineandReverseSkyline
QueriesUsingMapReduce
SeoulNationalUniversity
Seoul,Korea
YoonjaePark
KoreaUniv.ofTech.&Edu.
CheonAn,Korea
Jun-KiMin
SeoulNationalUniversity
Seoul,Korea
KyuseokShim
yjpark@kdd.snu.ac.kr
ABSTRACT
jkmin@kut.ac.krshim@ee.snu.ac.kr
Theskylineoperatoranditsvariantssuchasdynamicsky-lineandreverseskylineoperatorshaveattractedconsid-erableattentionrecentlyduetotheirbroadapplications.However,computationsofsuchoperatorsarechallengingtodaysincethereisanincreasingtrendofapplicationstodealwithbigdata.Forsuchdata-intensiveapplications,theMapReduceframeworkhasbeenwidelyusedrecently.Inthispaper,weproposee cientparallelalgorithmsforprocessingtheskylineanditsvariantsusingMapReduce.We rstbuildhistogramstoe ectivelypruneoutnon-skyline(non-reverseskyline)pointsinadvance.Wenextpartitiondatabasedontheregionsdividedbythehistogramsandcomputecandidate(reverse)skylinepointsforeachregionindependentlyusingMapReduce.Finally,wecheckwhethereachcandidatepointisactuallya(reverse)skylinepointineveryregionindependently.Ourperformancestudycon- rmsthee ectivenessandscalabilityoftheproposedalgo-rithms.
1.INTRODUCTION
Theskylineoperator[4]anditsvariantssuchasdynamicskyline[22]andreverseskyline[11]operatorshaverecentlyattractedconsiderableattentionduetotheirbroadapplica-tionsincludingproductorrestaurantrecommendations[18,19],reviewevaluationswithuserratings[17],queryingwire-lesssensornetworks[29]andgraphanalysis[33].
Theskylineisasetofallpointsthatarenotdominatedbyanyotherpoint.Apointpiissaidtodominateanotherpointpjifpiisnotgreaterthanpjinalldimensionsandpiissmallerthanpjinatleastasingledimension.ConsideralaptopdatabaseDwithpriceandweightattributesinFigure1(a).Auserwhowantstobuyalaptopcanconsiderthelaptopsintheskyline{p1,p3,p5,p7}only,sincetherealwaysexistsabetterlaptopintheskylineforanylaptopwhichisnotintheskyline.
Thedynamicskylineisasetofallpointsthatarenotdominatedbyanyotherpointwithrespectto(wrt)thedis-tancestoagivenquerypoint.Whenauserwantsto nda
Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe rstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspeci cpermissionand/orafee.ArticlesfromthisvolumewereinvitedtopresenttheirresultsatThe39thInternationalConferenceonVeryLargeDataBases,August26th-30th2013,RivadelGarda,Trento,Italy.ProceedingsoftheVLDBEndowment,Vol.6,No.14
Copyright2013VLDBEndowment2150-8097/13/14...$10.00.
laptopwhosepriceandweightarecloseto50and25respec-tively,thedynamicskylineofDwrtaquerypoint 50,25 canbeusefulcandidatelaptopstobepurchased.
Supposethateachpointpirepresentsauserwhopur-chasedalaptopinFigure1(a)andacompanywantstoes-timatethesalesofalaptoptobemanufacturedwhosepriceandweightwillbe50and25respectively.Ifq= 50,25 belongstothedynamicskylineofDwrtapointpi,wecanassumethattheuserpi ndsthelaptopqinteresting.ThereverseskylineofDwrtqisde nedasasetofeverypointpi∈DsuchthatqbelongstothedynamicskylineofDwrtpi.Thus,thereverseskylineofDwrtqisasetofallcustomerswhowillbeinterestedinq.
Computingtheskylineoritsvariantsischallengingtodaysincethereisanincreasingtrendofapplicationsexpectedtodealwithbigdata.Forexample,Wal-Marthasa4PB(that’s4×1015bytes)datawarehouseofpurchaserecordswithdozensofattributes[5]whereskylineanditsvariantoperatorsarefrequentlyusedasprimitiveoperatorstode-terminepricingandmarketingstrategies.Forsuchdata-intensiveapplications,theMapReduce[10]frameworkhasrecentlyattractedalotofattention.MapReduceisapro-grammingmodelthatallowseasydevelopmentofscalableparallelapplicationstoprocessbigdataonlargeclustersofcommoditymachines.Google’sMapReduceoritsopen-sourceequivalentHadoop[2]isapowerfultoolforbuildingsuchapplications.Recently,avariantofHadoopwasalsodevelopedtosupportonlinequeryprocessingin[9],whichenablesMapReducetobeutilizedforsuchapplicationsin-cludingeventmonitoringandstreamdataprocessing.
Mostofexistingserialalgorithms[4,7,15,22,25]for(re-verse)skylinecomputationsrelyonsomecentralizedindex-ingstructuressuchasB+-trees[8]orR -trees[3].However,intheMapReduceframework,thereisnofunctionalitypro-videdforbuildingandaccessingsuchspatialindexesbecauseitisdi culttoprovidee cientandscalabledistributedin-dexesinseveralthousandsofmachines.Thus,itishardtoextendsuchexistingalgorithmsintotheMapReduceframe-work.ApreliminaryworktoadaptskylineprocessingtotheMapReduceframeworkwasrecentlypresentedin[30].Theproposedalgorithmsaresimpleextensionsofpreviousserialskylinealgorithmsin[4,7,25].Furthermore,dynamicsky-lineandreverseskylineoperatorswerenotaddressedin[30].Inthispaper,weproposee cientparallelalgorithms,calledSKY-MRandRSKY-MR,whichcomputetheskylinesandreverseskylinesusingMapReducerespectively.Inthe rstphase,webuildnewhistograms,calledthesky-quadtreeandrsky-quadtree,whichareextensionsofquadtrees[12]
2002
MapReduce框架下的Skyline计算_专业资料。由于Skyline查询广泛应用于多目标决策、数据可视化等领域,近年来成为数据库领域的一个研究热点。针对云计算环境,在MapReduce...
Furthermore, we propose several interesting variations of skyline computation, ...Using the common exa 分享到: X 分享到: 使用一键分享,轻松赚取财富值, ...
Furthermore, we propose several interesting variations of skyline computation, ...Using the common exa 分享到: X 分享到: 使用一键分享,轻松赚取财富值, ...
热门文档