ParallelSubgraphListinginaLarge-ScaleGraph

摘要：

　　Subgraphlistingisafundamentaloperationtomanygraphandnetworkanalyses.Theproblemitselfiscomputationallyex pensiveandiswell-studiedincentralizedprocessingalgorithms.However,thecentralizedsolutionscannotscalewelltolarg egraphs.Recently, severalparallelapproachesareintroducedtohandlethelarge graphs.Unfortunately, theseparallelappr oachesstillrelyontheexpensivejoinoperations,thuscannotachievehighperformance.Inthispaper, wedesign anovelparallelsubgraphlisting framework,namedPSgL.ThePSgLiterativelyenumeratessu bgraphinstancesandsolvesthesubgraphlistinginadivide-and-conquerfashion.Theframeworkcompletelyreliesonthegr aphtraversal,andavoidstheexplicitjoinoperation.Moreover,inordertoimproveitsperformance,weproposeseveralsoluti onstobalancetheworkloadandreducethesizeofintermediateresults.Specially,weprovetheproblemofpartialsubgraphins tancedistributionforworkloadbalanceisNP-hard,andcarefullydesignasetofheuristicstrategies.Tofurthermeducetheenor mousintermediateresults,weintroducethreeindependentmechanisms,whichareautomorphismbreakingofthepatterngr aph,initialpatternvertexselectionbasedonacostmodel,andapruningmethodbasedonalight-weightindex.WehaveimplementedtheprototypeofPSgL,andruncomprehensive experimentsof various graphlisting operations on diverselargegraphs.TheexperimentsclearlydemonstratethatPSgLisrobustandcanachieveperformancegainovert hestate-of-the-artsolutionsupto90%.

关键词： Graph GraphAlgorithm SubgraphListing GraphEnumeration

作者: YingxiaSHAO BinCUI LeiCHEN LinMA JunjieYAO NingXU

会议类型: 国际会议

会议名称: 第十二届全国博士生学术年会——计算机科学与技术专题

会议地点: 昆明

会议语种:英文

页码: 275-292

在线出版日期: 2014-05-01（万方平台首次上网日期，不代表论文的发表时间）