文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce.2002-2013
侵权投诉

Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce.2002-2013

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email