大圖上高效的子圖匹配算法設(shè)計與實現(xiàn)

1、另囂聲夕擎分類號UDC●■●密級公玨碩士研究生學(xué)位論文大圖上高效的子圖匹配算法設(shè)計與實現(xiàn)申請人：紀(jì)安娜學(xué)號：2141353培養(yǎng)單位：計算機科學(xué)技術(shù)學(xué)院學(xué)科專業(yè)：軟件工程研究方向：數(shù)據(jù)挖掘指導(dǎo)教師：楊艷教授完成日期：2016年3月26日萬方數(shù)據(jù)黑龍江大學(xué)碩士學(xué)位論文AbstractIntheeraofbigdata，thereisamassivemulti—sourceandheterogeneousdatawithcomplexandc

2、loserelationships，usingthegraphstructureasdescribedcomplexrelationshipsamongdataarewidelyusedinvariousfieldsHoweverwiththerapiddevelopmentofthesefields，theamountofdatausinggraphstructureisalsoexponentiallyexplodingAndsub

3、graphmatchingasthebasicoperationingraphprocessing，getabundantattentionfromacademiaandindustryRecentlyhowtoefficientbaseonuserdefinedquerystructuretogetmatcheswhichmeetuser—definedrequirementsonlarge—scalegraphbecomeaprim

4、aryproblemAndpreviousworkonsubgraphmatchingdon’tconsideruser—definedrequirementsforsomespecialedgesSOtheyarepowerlessagainstquerygraphswithweightsandexistingalgorithmsarenotsuitableforlarge—scalegraphsInthispaperitdoesso

5、meimprovementandinnovationintheshortcomingsofsubgraphmatchingThemainresearchachievementsandcontributionsareasfollows：Personalizedsubgraphmatchinginlarge—scalegraphsisdiscussedFirstlywepartitionthelargegraphintosomesub—re

6、gionsbyGNalgorithmandbuidtwoindexstructures：GP—TreeandSortedList(SL)indexwhichareconstructedoffiineThen，basedontheindexstructures，weuseoptimizationstrategiesintoourmethodtoacceleratesubgraphmatchingFinallyourexperimental

7、resultsevaluatetheefficiencyandscalabilityofourproposedmethodParallelpersonalizedsubgraphmatchinginlarge—ScalegraphisdiscussedFirstlywepartitionthelargegraphbytheSparkGraphX’SVertex—Cutalgorithmandbuildtwoindexstructures