北大 分布式系统powergraph.pptx

Joseph Gonzalez Yucheng Low Danny Bickson Distributed Graph-putation on Natural Graphs Haijie Gu Joint work with: Carlos Guestrin PowerGraph 2 Graphs are ubiquitous.. 2 3 Social Media ? Graphs encode relationships between: ? Big : billions of vertices and edges and rich metadata Advertising Science Web People Facts Products Interests Ideas 4 Graphs are Essential to Data-Mining and Machine Learning ? Identify influential people and information ? munities ? Target ads and products ? plex data dependencies 4 5 Natural Graphs Graphs derived from natural phenomena 6 6 Problem: Existing distributed graph computation systems perform poorly on Natural Graphs . 7 PageRank on Twitter Follower Graph Natural Graph with 40M Users, Billion Links Hadoop results from [Kang et al. '11 ] Twister (in-memory MapReduce ) [ Ekanayake et al. ‘10] 7 O rder of magnitude by exploiting properties of Natural Graphs PowerGraph 8 Properties of Natural Graphs 8 Power-Law Degree Distribution 10 Power-Law Degree Distribution 10“ Star Like ” Motif President Obama Followers