際際滷

際際滷Share a Scribd company logo

SDEC2011 Implementing me2day friend suggestion

K
Korea Sdec

In the SNS domain, Response time of Friend Suggestion Algorithms and several SNA algorithms is in direct proportion to square of relationship number. In addition, increasing rate of relationship number is bigger and bigger. But existing usage pattern of Relational DB is suffering poor performance. To guarantee performance and scalability, we have developed such methods for Friend Suggestion and SNA Relation Pruning using intimacy value No Join & Keeping all Data in-Memory Strategy Distributed Graph Structure

1 of 38
Downloaded 147 times
Implementing me2day Friend Suggestion NHN 覩誤一伎誤手覦 螳語 1
Implementing me2day Friend Suggestion NHN 覩誤一伎誤手覦 螳語 2
Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 豺蟲豢豌 ろ 蟲 蟆磯 覦 ロ 3
4
5
螳 豺蟲 伎 .. 覩語 譬 蠏企慨! 覿り 4覈 豌 譯手.. 蠏碁 覲企誤 願.. 覿 覿! ! 覩誤 螳 谿伎. 6
SNS 豺蟲豢豌 蟆 襦 豺蟲襯 蠏 襦 譯朱 レ 豺蟲螳 蟆 豺蟲豢豌 SNS = 觚襦蠏? 豺蟲豌 企骸蟾? 伎 SNS 覓覩碁ゼ 蟆~ 7
me2day 豺蟲豢豌 8
me2day 豺蟲豢豌 豢豌 螻牛給 豺蟲 9
Next Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 Friend of a Friend 豢豌 Close Friend of a Close Friend 豢豌 豺蟲豢豌 ろ 蟲 蟆磯 覦 ロ 10
Friend of a Friend (FOAF) 豢豌 F(A, B) = A, B螳 豺蟲蟯螻企 True M.F.C(A, C) = A, C 螻牛旧蟲 (Mutual Friend Count) A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 螳螳 C襷 M.F.C(A, C)螳 朱 First 豺蟲1 伎 螳蠍語企 豺蟲2 讌ル襭 豺蟲3 ル Jilin Chen, (2009), Recommending People on Social Networking Sites. 11
Friend of a Friend (FOAF) 豢豌 F(A, B) = A, B螳 豺蟲蟯螻企 True M.F.C(A, C) = A, C 螻牛旧蟲 (Mutual Friend Count) A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 螳螳 C襷 M.F.C(A, C)螳 朱 豺蟲1 伎 螳蠍語企 豺蟲2 讌ル襭 Second 豺蟲3 ル Jilin Chen, (2009), Recommending People on Social Networking Sites. 12
Friend of a Friend (FOAF) 豢豌 F(A, B) = A, B螳 豺蟲蟯螻企 True M.F.C(A, C) = A, C 螻牛旧蟲 (Mutual Friend Count) A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 螳螳 C襷 M.F.C(A, C)螳 朱 豺蟲1 伎 Third 螳蠍語企 豺蟲2 讌ル襭 豺蟲3 ル Jilin Chen, (2009), Recommending People on Social Networking Sites. 13
Close Friend of a Close Friend (CFOACF) 豢豌 FOAF 豢豌 螻襴讀 豺覦襯 豢螳 螻襴讀 A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 I(A, B) = A B 豺覦 (A B襦 給 豺襦 ) Score of C = I(A, Bi) * I(Bi, C) 2 9 1 豺蟲1 1 伎 1 5 螳蠍語企 豺蟲2 讌ル襭 2 豺蟲3 ル 14
Close Friend of a Close Friend (CFOACF) 豢豌 FOAF 豢豌 螻襴讀 豺覦襯 豢螳 螻襴讀 A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 I(A, B) = A B 豺覦 (A B襦 給 豺襦 ) Score of C = I(A, Bi) * I(Bi, C) 豺蟲1 伎 5 螳蠍語企 豺蟲2 2 讌ル襭 2 16 3 豺蟲3 ル 15
Close Friend of a Close Friend (CFOACF) 豢豌 FOAF 豢豌 螻襴讀 豺覦襯 豢螳 螻襴讀 A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 I(A, B) = A B 豺覦 (A B襦 給 豺襦 ) Score of C = I(A, Bi) * I(Bi, C) 豺蟲1 伎 5 4 20 螳蠍語企 豺蟲2 讌ル襭 豺蟲3 ル 16
Close Friend of a Close Friend (CFOACF) 豢豌 豺覦 螳 一 襦語 蟯豺蟲, 蠍, 覩誤, 豺蟲 襷碕 蠍郁 Feedback !! 17
Next Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 豺蟲豢豌 ろ 蟲 Social Network 一危 覈碁 Graph Product 螻 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 豺蟲豢豌 ろ レ 覓語 蟆磯 覦 ロ 18
Social Network 一危 覈碁 Social Network 覈碁 蠍磯 觜蟲 <Social Network> 5 3 <Relational Model> user_no friend_no 1 8 2 1 5 1 9 9 6 <Graph Model> 1 8 2 3 User Nodes 2 8 1 5-9-8 3 5 2 3-8 3 8 3 5-8-9-2 List of 3 9 5 8-1-3 Friend 3 2 6 9-8 . . 8 1-5-3-2-6 . . 9 1-3-6 . . 9 6 19
Social Network 一危 覈碁 Relational Model 貎朱Μ 覦覯 <User, Friend> Join or 貎朱Μ 20
Social Network 一危 覈碁 Graph Model 貎朱Μ 覦覯 Just Tracking Reference Pointer ! 21
Social Network 一危 覈碁 ろ: 25襷 覈 豺蟲襯 螳讌 豺蟲 豺蟲 蟲蠍 Result (Count : 9,060,712) Relational Model Graph Model Response 5.9 sec 40X 0.15 sec Time 22
Graph Product 螻 Graph Products Features Comparisons Graph Framework Graph Database Data Durability Medium-Low Medium-High Cache hit-ratio 100 % Depend on Workload Suitable Workload Batch Job Real-time Job TinkerPops TinkerGraph Neo Techs Neo4j Products Googles Pregel Twitters FlockDB MSs Trinity Orient Techs OrientDB Google, Inc, (2010), Pregel : A System for Large-Scale Graph Processing http://www.tinkerpop.com/, http://www.graph-database.org/ 23
Graph Product 螻 Graph Products Evaluation High FlockDB Pregel Neo4j OrientDB Availability TinkerGraph Low Low High Performance http://markorodriguez.com, http://www.orientechnologies.com/ 24
Graph Product 螻 豺蟲豢豌 ろ 蟲 TinkerGraph 蟲覦 谿瑚 Availability レ Replication Failover 蠍磯 蟲 Stand-by Master Batch Server Batch Server Friendships Suggestion Result 25
豺蟲螳 襷 襦 誤 焔レ 蠏豪概 豺蟲螳 襷 覲語瑚骸 豺蟲れ 豢豌 一一 焔レ 企 豺蟲 蠍蟆 襦 讀螳螻 265 X 26
豺蟲螳 襷 襦 誤 焔レ 蠏豪概 Dunbars Number 豺覦 蟯螻 螻 150覈~200覈 企朱 企 豺蟲 襷 覺 讌讌 豺蟲 150覈伎!~ Robin Dunbar, (2010), How Many friends Does One Person Need?. 27
豺蟲螳 襷 襦 誤 焔レ 蠏豪概 豺覦 朱 150覈襷 蟆螻 襾語 蟇 28
豺蟲螳 襷 襦 誤 焔レ 蠏豪概 Result Graph Graph Relational (All) (Top 150) Response 5.9 sec 0.15 sec 0.0005 sec Time 40X 300X 29
豺蟲螳 襷 襦 誤 焔レ 蠏豪概 Result All Top 150 Result 9,060,712 14,912 Count 99% Memory 900 MB 608 MB 32% Load 37.1 sec 28.8 sec Time 23% 30
豺蟲豢豌 ろ レ 覓語 Social Network 蠍蟆 煙 Batch Server Batch Server Batch Server ! 1 覃覈襴襯 願覃 伎讌? 31
豺蟲豢豌 ろ レ 覓語 1 覃覈襴襯 伎 一危磯 SSD 貂 螻襴讀(LRU, LFU) 磯 覃覈襴 一危磯ゼ 讌 Batch Server Batch Server SSD 32
豺蟲豢豌 ろ レ 覓語 2 蠏碁襯 覿襯 螻襴讀朱 覿壱伎 Local 覃覈襴 miss Remote Cache Cloud襯 谿語＾ Batch Server 1 Batch Server 2 Batch Server 3 Batch Server 4 Remote Cache Cloud 33
Next Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 豺蟲豢豌 ろ 蟲 ∬屋襦 覦 ロ 34
蟆磯 覦 ロ 豺蟲豢豌 ろ 蟲 れ 覦れ Graph Model Pruning Edges using Dunbars Number Scalable Distributed Architecture ろ 蠏 豺蟲蟯螻 20%螳 豺蟲豢豌朱 襷碕伎螻 豢豌 螻襴讀 蟲 Scalability 覲企 螻 讌 譴 35
36
谿瑚覓誤 Jilin Chen, (2009), Recommending People on Social Networking Sites. Robin Dunbar, (2010), How Many friends Does One Person Need. RENZO ANGLES, (2008), Survey of Graph database models, ACM Computing Surveys. Marko A. Rodriguez, (2010), Graph Traversal Programming Pattern. HANNEMAN, R. A, (2001), Introduction to social network methods. TinkerPop, TinkerGraph. http://github.com/tinkerpop/gremlin/wiki/tinkergraph Grzegorz Malewicz, (2010), Pregel : A System for Large-Scale Graph Processing, Google, Inc. Microsoft, Trinity, http://research.microsoft.com/en-us/projects/trinity/ 37
谿瑚覓誤 Neo Technology, Neo4j : the Graph database. www.neo4j.org Twitter, FlockDB, https://github.com/twitter/flockdb/blob/master/doc/blog.md Orient Technologies, OrientDB, http://www.orientechnologies.com/ Marko A. Rodriguez, MySQL vs. Neo4j on a Large-Scale Graph Traversal, http://markorodriguez.com/2011/02/18/mysql-vs-neo4j-on-a-large-scale- graph-traversal/ 38

More Related Content

SDEC2011 Implementing me2day friend suggestion

  • 1. Implementing me2day Friend Suggestion NHN 覩誤一伎誤手覦 螳語 1
  • 2. Implementing me2day Friend Suggestion NHN 覩誤一伎誤手覦 螳語 2
  • 3. Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 豺蟲豢豌 ろ 蟲 蟆磯 覦 ロ 3
  • 4. 4
  • 5. 5
  • 6. 螳 豺蟲 伎 .. 覩語 譬 蠏企慨! 覿り 4覈 豌 譯手.. 蠏碁 覲企誤 願.. 覿 覿! ! 覩誤 螳 谿伎. 6
  • 7. SNS 豺蟲豢豌 蟆 襦 豺蟲襯 蠏 襦 譯朱 レ 豺蟲螳 蟆 豺蟲豢豌 SNS = 觚襦蠏? 豺蟲豌 企骸蟾? 伎 SNS 覓覩碁ゼ 蟆~ 7
  • 9. me2day 豺蟲豢豌 豢豌 螻牛給 豺蟲 9
  • 10. Next Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 Friend of a Friend 豢豌 Close Friend of a Close Friend 豢豌 豺蟲豢豌 ろ 蟲 蟆磯 覦 ロ 10
  • 11. Friend of a Friend (FOAF) 豢豌 F(A, B) = A, B螳 豺蟲蟯螻企 True M.F.C(A, C) = A, C 螻牛旧蟲 (Mutual Friend Count) A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 螳螳 C襷 M.F.C(A, C)螳 朱 First 豺蟲1 伎 螳蠍語企 豺蟲2 讌ル襭 豺蟲3 ル Jilin Chen, (2009), Recommending People on Social Networking Sites. 11
  • 12. Friend of a Friend (FOAF) 豢豌 F(A, B) = A, B螳 豺蟲蟯螻企 True M.F.C(A, C) = A, C 螻牛旧蟲 (Mutual Friend Count) A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 螳螳 C襷 M.F.C(A, C)螳 朱 豺蟲1 伎 螳蠍語企 豺蟲2 讌ル襭 Second 豺蟲3 ル Jilin Chen, (2009), Recommending People on Social Networking Sites. 12
  • 13. Friend of a Friend (FOAF) 豢豌 F(A, B) = A, B螳 豺蟲蟯螻企 True M.F.C(A, C) = A, C 螻牛旧蟲 (Mutual Friend Count) A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 螳螳 C襷 M.F.C(A, C)螳 朱 豺蟲1 伎 Third 螳蠍語企 豺蟲2 讌ル襭 豺蟲3 ル Jilin Chen, (2009), Recommending People on Social Networking Sites. 13
  • 14. Close Friend of a Close Friend (CFOACF) 豢豌 FOAF 豢豌 螻襴讀 豺覦襯 豢螳 螻襴讀 A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 I(A, B) = A B 豺覦 (A B襦 給 豺襦 ) Score of C = I(A, Bi) * I(Bi, C) 2 9 1 豺蟲1 1 伎 1 5 螳蠍語企 豺蟲2 讌ル襭 2 豺蟲3 ル 14
  • 15. Close Friend of a Close Friend (CFOACF) 豢豌 FOAF 豢豌 螻襴讀 豺覦襯 豢螳 螻襴讀 A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 I(A, B) = A B 豺覦 (A B襦 給 豺襦 ) Score of C = I(A, Bi) * I(Bi, C) 豺蟲1 伎 5 螳蠍語企 豺蟲2 2 讌ル襭 2 16 3 豺蟲3 ル 15
  • 16. Close Friend of a Close Friend (CFOACF) 豢豌 FOAF 豢豌 螻襴讀 豺覦襯 豢螳 螻襴讀 A 豢豌豺蟲 讌 = F(A, B) 願 F(B, C) Cれ 讌 I(A, B) = A B 豺覦 (A B襦 給 豺襦 ) Score of C = I(A, Bi) * I(Bi, C) 豺蟲1 伎 5 4 20 螳蠍語企 豺蟲2 讌ル襭 豺蟲3 ル 16
  • 17. Close Friend of a Close Friend (CFOACF) 豢豌 豺覦 螳 一 襦語 蟯豺蟲, 蠍, 覩誤, 豺蟲 襷碕 蠍郁 Feedback !! 17
  • 18. Next Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 豺蟲豢豌 ろ 蟲 Social Network 一危 覈碁 Graph Product 螻 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 豺蟲豢豌 ろ レ 覓語 蟆磯 覦 ロ 18
  • 19. Social Network 一危 覈碁 Social Network 覈碁 蠍磯 觜蟲 <Social Network> 5 3 <Relational Model> user_no friend_no 1 8 2 1 5 1 9 9 6 <Graph Model> 1 8 2 3 User Nodes 2 8 1 5-9-8 3 5 2 3-8 3 8 3 5-8-9-2 List of 3 9 5 8-1-3 Friend 3 2 6 9-8 . . 8 1-5-3-2-6 . . 9 1-3-6 . . 9 6 19
  • 20. Social Network 一危 覈碁 Relational Model 貎朱Μ 覦覯 <User, Friend> Join or 貎朱Μ 20
  • 21. Social Network 一危 覈碁 Graph Model 貎朱Μ 覦覯 Just Tracking Reference Pointer ! 21
  • 22. Social Network 一危 覈碁 ろ: 25襷 覈 豺蟲襯 螳讌 豺蟲 豺蟲 蟲蠍 Result (Count : 9,060,712) Relational Model Graph Model Response 5.9 sec 40X 0.15 sec Time 22
  • 23. Graph Product 螻 Graph Products Features Comparisons Graph Framework Graph Database Data Durability Medium-Low Medium-High Cache hit-ratio 100 % Depend on Workload Suitable Workload Batch Job Real-time Job TinkerPops TinkerGraph Neo Techs Neo4j Products Googles Pregel Twitters FlockDB MSs Trinity Orient Techs OrientDB Google, Inc, (2010), Pregel : A System for Large-Scale Graph Processing http://www.tinkerpop.com/, http://www.graph-database.org/ 23
  • 24. Graph Product 螻 Graph Products Evaluation High FlockDB Pregel Neo4j OrientDB Availability TinkerGraph Low Low High Performance http://markorodriguez.com, http://www.orientechnologies.com/ 24
  • 25. Graph Product 螻 豺蟲豢豌 ろ 蟲 TinkerGraph 蟲覦 谿瑚 Availability レ Replication Failover 蠍磯 蟲 Stand-by Master Batch Server Batch Server Friendships Suggestion Result 25
  • 26. 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 豺蟲螳 襷 覲語瑚骸 豺蟲れ 豢豌 一一 焔レ 企 豺蟲 蠍蟆 襦 讀螳螻 265 X 26
  • 27. 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 Dunbars Number 豺覦 蟯螻 螻 150覈~200覈 企朱 企 豺蟲 襷 覺 讌讌 豺蟲 150覈伎!~ Robin Dunbar, (2010), How Many friends Does One Person Need?. 27
  • 28. 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 豺覦 朱 150覈襷 蟆螻 襾語 蟇 28
  • 29. 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 Result Graph Graph Relational (All) (Top 150) Response 5.9 sec 0.15 sec 0.0005 sec Time 40X 300X 29
  • 30. 豺蟲螳 襷 襦 誤 焔レ 蠏豪概 Result All Top 150 Result 9,060,712 14,912 Count 99% Memory 900 MB 608 MB 32% Load 37.1 sec 28.8 sec Time 23% 30
  • 31. 豺蟲豢豌 ろ レ 覓語 Social Network 蠍蟆 煙 Batch Server Batch Server Batch Server ! 1 覃覈襴襯 願覃 伎讌? 31
  • 32. 豺蟲豢豌 ろ レ 覓語 1 覃覈襴襯 伎 一危磯 SSD 貂 螻襴讀(LRU, LFU) 磯 覃覈襴 一危磯ゼ 讌 Batch Server Batch Server SSD 32
  • 33. 豺蟲豢豌 ろ レ 覓語 2 蠏碁襯 覿襯 螻襴讀朱 覿壱伎 Local 覃覈襴 miss Remote Cache Cloud襯 谿語＾ Batch Server 1 Batch Server 2 Batch Server 3 Batch Server 4 Remote Cache Cloud 33
  • 34. Next Contents SNS 豺蟲豢豌 豺蟲豢豌 螻襴讀 豺蟲豢豌 ろ 蟲 ∬屋襦 覦 ロ 34
  • 35. 蟆磯 覦 ロ 豺蟲豢豌 ろ 蟲 れ 覦れ Graph Model Pruning Edges using Dunbars Number Scalable Distributed Architecture ろ 蠏 豺蟲蟯螻 20%螳 豺蟲豢豌朱 襷碕伎螻 豢豌 螻襴讀 蟲 Scalability 覲企 螻 讌 譴 35
  • 36. 36
  • 37. 谿瑚覓誤 Jilin Chen, (2009), Recommending People on Social Networking Sites. Robin Dunbar, (2010), How Many friends Does One Person Need. RENZO ANGLES, (2008), Survey of Graph database models, ACM Computing Surveys. Marko A. Rodriguez, (2010), Graph Traversal Programming Pattern. HANNEMAN, R. A, (2001), Introduction to social network methods. TinkerPop, TinkerGraph. http://github.com/tinkerpop/gremlin/wiki/tinkergraph Grzegorz Malewicz, (2010), Pregel : A System for Large-Scale Graph Processing, Google, Inc. Microsoft, Trinity, http://research.microsoft.com/en-us/projects/trinity/ 37
  • 38. 谿瑚覓誤 Neo Technology, Neo4j : the Graph database. www.neo4j.org Twitter, FlockDB, https://github.com/twitter/flockdb/blob/master/doc/blog.md Orient Technologies, OrientDB, http://www.orientechnologies.com/ Marko A. Rodriguez, MySQL vs. Neo4j on a Large-Scale Graph Traversal, http://markorodriguez.com/2011/02/18/mysql-vs-neo4j-on-a-large-scale- graph-traversal/ 38