资源描述：
《wang_managing and mining billion-node graphsnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、KDD2012SummerSchoolManagingandMiningBillion-NodeGraphsHaixunWangMicrosoftResearchAsia1OurFocusSystem&GraphProcessing2Outline•LargeGraphChallenges•SystemsforLargeGraphs–RDBMS,MapReduce,Pregel,Pegasus,Trinity•KeyGraphAlgorithms–GraphPartitioning,Traversal,Query,Analytics3Out
2、line•LargeGraphChallenges•SystemsforLargeGraphs–RDBMS,MapReduce,Pregel,Pegasus,Trinity•KeyAlgorithms–GraphPartitioning,Traversal,Query,Analytics4Graphsencoderichrelationshipstrillion8#ofEdgesDeBrujinGraphtrillion1theWebbillion104Facebookbillion31LinkedDatabillion5.6million
3、58USRoadMap#ofNodes245048001.4501millionmillionmillionbillionbilliontrillion5DiversityofGraphsP(k)~k-aScaleFreeGraphsCommunityStructureSmallWorld6ALargeVarietyofGraphOperations•Onlinequeryprocessing–Shortestpathquery–Subgraphmatchingquery–SPARQLquery–…•Offlinegraphanalytic
4、s–PageRank–Communitydetection–…•Othergraphoperations–Graphgeneration,visualization,interactiveexploration,etc.7CurrentStatus•Goodsystemsforprocessinggraphs:–PBGL,Neo4j•Goodsystemsforprocessinglargedata:–Map/Reduce,Hadoop•Goodsystemsforprocessingspecializedlargegraphdata:–S
5、pecializedsystemsforpagerank,etc.8Thisishard.GeneralityGraphLargeDataDataNogoodsystemforprocessinggenerallargegraphs9Graphprocessingwithoutasystemishard!FundamentalissuesDifferentprogrammingmodelsscheduling,datadistribution,synchronization,inter-processcommunication,robust
6、ness,faulttolerance,MessagePassingSharedMemory…MemoryArchitecturalissuesP1P2P3P4P5P1P2P3P4P5Flynn’staxonomy(SIMD,MIMD,etc.),networktypology,bisectionbandwidthUMAvs.NUMA,cachecoherenceCommonproblemslivelock,deadlock,datastarvation,priorityinversion…diningphilosophers,sleepi
7、ngbarbers,cigarettesmokers,…producerconsumerDifferentprogrammingconstructsmastermutexes,conditionalvariables,barriers,…masters/slaves,producers/consumers,workqueues,…slavesworkqueueproducerconsumerProgrammershoulderstheburdenofmanagingallthesesubtleissues…Adaptedfrom:Jimmy
8、Lin,SIKS/BigGridBigDataTutorial(2011)Benefitsofageneralpurposesystem•Enableapplicationsto
