-
Notifications
You must be signed in to change notification settings - Fork 1
/
Nynn.mm
81 lines (81 loc) · 6.88 KB
/
Nynn.mm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
<map version="1.0.0">
<!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net -->
<node CREATED="1392968875051" ID="ID_1356508968" MODIFIED="1409883060302" TEXT="nynn">
<node CREATED="1409883063313" ID="ID_1266871386" MODIFIED="1409883602478" POSITION="right" TEXT="a large-scale sparse graph">
<node CREATED="1409883120781" ID="ID_186986950" MODIFIED="1409883126931" TEXT="billions of edges"/>
<node CREATED="1409883106601" ID="ID_856898726" MODIFIED="1409883265816" TEXT="billions of vertices"/>
<node CREATED="1409883127709" ID="ID_249094871" MODIFIED="1409883149200" TEXT="mean outgoing degree"/>
<node CREATED="1409883306290" ID="ID_549621372" MODIFIED="1409883318215" TEXT="for an example">
<node CREATED="1409883323109" ID="ID_1742917425" MODIFIED="1409883429059" TEXT="twitter has X user, mean number of each user's followers is Y"/>
<node CREATED="1409883344743" ID="ID_1020476309" MODIFIED="1409883441391" TEXT="sina ..."/>
</node>
</node>
<node CREATED="1409886197393" ID="ID_1769692974" MODIFIED="1409886202150" POSITION="right" TEXT="conclusion">
<node CREATED="1409886203677" ID="ID_339473594" MODIFIED="1409886227256" TEXT="random access vertex"/>
<node CREATED="1409886882570" ID="ID_1584769547" MODIFIED="1409886898420" TEXT="all-in-memory computation"/>
<node CREATED="1409886913365" ID="ID_1880541639" MODIFIED="1409886930387" TEXT="quasi realtime incremental updating"/>
<node CREATED="1409886993676" ID="ID_1082715315" MODIFIED="1409887028931" TEXT="local read: memory-level throughput"/>
<node CREATED="1409887029849" ID="ID_1057846009" MODIFIED="1409887092883" TEXT="remote read: occupy all bandwidth"/>
</node>
<node CREATED="1409883594548" ID="ID_1349839368" MODIFIED="1409883639140" POSITION="right" TEXT="graph computation">
<node CREATED="1409883604629" ID="ID_212769993" MODIFIED="1409883612788" TEXT="iterative"/>
<node CREATED="1409883612960" ID="ID_198215029" MODIFIED="1409883620764" TEXT="data intensive"/>
<node CREATED="1409883627375" ID="ID_1303175353" MODIFIED="1409883634683" TEXT="random access vertex"/>
</node>
<node CREATED="1409883292618" ID="ID_1947381052" MODIFIED="1409883450192" POSITION="right" TEXT="nynn file system ">
<node CREATED="1409883460923" ID="ID_833004931" MODIFIED="1409883518815" TEXT="a nynn file represents an vertex and all of its outgoing edges"/>
<node CREATED="1409883528756" ID="ID_1508048914" MODIFIED="1409883580423" TEXT="vertex represents user, edge represents link between two users"/>
</node>
<node CREATED="1409883587230" ID="ID_1949874272" MODIFIED="1409884886388" POSITION="right" TEXT="design">
<node CREATED="1409883661641" ID="ID_260617539" MODIFIED="1409883684447" TEXT="support large scale small files">
<node CREATED="1409883696592" ID="ID_851744097" MODIFIED="1409883820835" TEXT="the amount of files: large-scale"/>
<node CREATED="1409883708386" ID="ID_230834207" MODIFIED="1409883844376" TEXT="file size: small"/>
</node>
<node CREATED="1409883688723" ID="ID_823763427" MODIFIED="1409883882622" TEXT="addressing"/>
<node CREATED="1409883887363" ID="ID_1465719046" MODIFIED="1409883891405" TEXT="prefetch"/>
</node>
<node CREATED="1409884031445" ID="ID_217341233" MODIFIED="1409884033740" POSITION="right" TEXT="problem">
<node CREATED="1409884034750" ID="ID_522463924" MODIFIED="1409884629224" TEXT="quasi realtime incremental updating"/>
<node CREATED="1409884120498" ID="ID_927178337" MODIFIED="1409884245412" TEXT="random access vertices"/>
</node>
<node CREATED="1409884314801" ID="ID_1381754170" MODIFIED="1409884359874" POSITION="right" TEXT="storage of large-scale sparse graph"/>
<node CREATED="1409884505088" ID="ID_656380288" MODIFIED="1409884955435" POSITION="right" TEXT="solution">
<node CREATED="1409884525891" ID="ID_1560820578" MODIFIED="1409884551426" TEXT="gfs-like dfs">
<node CREATED="1409884741939" ID="ID_1475957505" MODIFIED="1409884803028" TEXT="graph must be preprocessing offline to fit in dfs"/>
</node>
<node CREATED="1409884552059" ID="ID_770860220" MODIFIED="1409884657456" TEXT="trinity distributed graph storage"/>
<node CREATED="1409884668128" ID="ID_81625436" MODIFIED="1409884671824" TEXT="neo4j"/>
<node CREATED="1409884663117" ID="ID_650504709" MODIFIED="1409884667855" TEXT="redis"/>
</node>
<node CREATED="1409884945640" ID="ID_1982719453" MODIFIED="1409884966880" POSITION="right" TEXT="file organization and address">
<node CREATED="1409884988286" ID="ID_1297964420" MODIFIED="1409885008569" TEXT="graph divided into subgraph"/>
<node CREATED="1409885012889" ID="ID_1180563355" MODIFIED="1409885077057" TEXT="vertices divided into intervals of same width"/>
<node CREATED="1409885346421" ID="ID_1760549412" MODIFIED="1409885596372" TEXT="all the vertices in the identical interval has the same sgkey, vertexID can translated to its sgkey by modulo interval width"/>
<node CREATED="1409885085095" ID="ID_424024741" MODIFIED="1409885213062" TEXT="easy to place vertex on subgraph"/>
<node CREATED="1409885216334" ID="ID_1686350493" MODIFIED="1409885227235" TEXT="easy to address subgraph"/>
<node CREATED="1409885227468" ID="ID_522327326" MODIFIED="1409885846686" TEXT="every vertex"/>
</node>
<node CREATED="1409884967742" ID="ID_1174177924" MODIFIED="1409885896459" POSITION="right" TEXT="graph data exceed memory">
<node CREATED="1409885897937" ID="ID_1578861975" MODIFIED="1409885937287" TEXT="overflow mechanism"/>
</node>
<node CREATED="1409885938854" ID="ID_1111906158" MODIFIED="1409885983045" POSITION="right" TEXT="data prefetch"/>
<node CREATED="1409885996141" ID="ID_366029467" MODIFIED="1409886002032" POSITION="right" TEXT="meta data">
<node CREATED="1409886631683" ID="ID_511334914" MODIFIED="1409886702956" TEXT="subgraph to machine mapping"/>
<node CREATED="1409886707762" ID="ID_989569266" MODIFIED="1409886707762" TEXT=""/>
</node>
<node CREATED="1409886006946" ID="ID_1082155308" MODIFIED="1409886019148" POSITION="right" TEXT="fault tolerance"/>
<node CREATED="1409886062252" ID="ID_1325258162" MODIFIED="1409886073261" POSITION="right" TEXT="consistency">
<node CREATED="1409886093666" ID="ID_1470197509" MODIFIED="1409886104568" TEXT="eventually consistent"/>
</node>
<node CREATED="1409886121014" ID="ID_365958703" MODIFIED="1410227226399" POSITION="right" TEXT="related work">
<node CREATED="1409886132547" ID="ID_304659333" MODIFIED="1409886135823" TEXT="redis"/>
<node CREATED="1409886136068" ID="ID_840456500" MODIFIED="1409886138734" TEXT="neo4j"/>
<node CREATED="1409886139016" ID="ID_1447164723" MODIFIED="1409886149790" TEXT="trinity"/>
</node>
<node CREATED="1409886154196" ID="ID_1614125357" MODIFIED="1409886156076" POSITION="right" TEXT="future">
<node CREATED="1409886477189" ID="ID_1030957306" MODIFIED="1409886489267" TEXT="store many graph instance"/>
<node CREATED="1409886489800" ID="ID_1266598886" MODIFIED="1409886511713" TEXT="write and read concurrency"/>
<node CREATED="1409886512186" ID="ID_970909126" MODIFIED="1409886595166" TEXT="graph partition: virtual vertex and physical vertex"/>
</node>
</node>
</map>