optimizing path query performance graph clustering strategies

《optimizing path query performance graph clustering strategies》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、OptimizingPathQueryPerformance:GraphClusteringStrategiesyzxYun-WuHuangNingJingElkeA.RundensteinerIBMT.J.WatsonLabsChangshaInstituteofTechnologyWorcesterPolytechnicInstituteywh@us.ibm.comjning@eecs.umich.edurundenst@cs.wpi.eduAbstractPathqueriesovertransportationnetworksareoperations

2、requiredbymanyGeographicInformationSystemsapplications.Suchnetworks,typicallymodeledasgraphscomposedofnodesandlinksandrepresentedaslinkrelations,canbeverylargeandhenceoftenneedtobestoredonsecondarystor-agedevices.PathquerycomputationoversuchlargepersistentnetworksamountstohighI/Ocost

3、sduetohavingtorepeatedlybringinlinksfromthelinkrelationfromsecondarystorageintothemainmemorybuerforprocessing.Thispaperisthersttopresentacomparativeexperimentalevaluationofalternativegraphclusteringsolutionsinordertoshowtheireectivenessinpathqueryprocessingovertransportationnetwor

4、ks.Clusteringoptimizationisattractivebecauseitdoesnotincuranyrun-timecost,requiresnoauxiliarydatastructures,andiscomplimentarytomanyoftheexistingsolutionsonpathqueryprocessing.Inthispaper,wedevelopanovelclusteringtech-nique,calledspatialpartitionclustering(SPC),thatexploitsuniqueprop

5、ertiesoftransportationnetworkssuchasspatialcoordinatesandhighlocality.Weidentifyotherpromisingcandidatesforclusteringoptimizationsfromtheliterature,suchastwo-waypartitioningandapproximatetopo-logicalclustering.Wene-tunethemtooptimizetheirI/Obehaviorforpathqueryprocessing.Ourexperime

6、ntalevaluationoftheperformanceofthesegraphclusteringtechniquesusinganactualcityroadnetworkaswellasrandomlygeneratedgraphsconsidersvariationsinparameterssuchasmemorybuersize,lengthofthepaths,locality,andout-degree.Ourexperimentalresultsarethefoundationforestablishingguidelinestoselec

7、tthebestclusteringtechniquebasedonthetypeofnetworks.WendthatourSPCperformsthebestforthehighlyinterconnectedcitymap;thehybridapproachforrandomgraphswithhighlocality;andthetwo-waypartitioningbasedonlinkweightsforrandomgraphswithnolocality.IndexTerms

8、PathQueryProcessing,TransportationN

9、etworks,Spat