amplab/graphx — pull request #41 by jegonzal (2013-10-31 03:13:56+00:00)
Title: Optimizing Graph Lineage

I added some code to `GraphImpl` to enable lineage printing. Here is the output after initial graph construction (I have added additional annotation):

```scala

val g = GraphLoader.textFile(sc, "/Users/jegonzal/Data/google.tsv", a => 1.0, 4, 4)
g.printLineage

// Exiting paste mode, now interpreting.

eTable ------------------------------------------
14: Memory Deserialized 1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@4c40b1b1), 4)
|---> Deps: List((org.apache.spark.OneToOneDependency@395e7bc4,13))
|---> PrefLoc: List(), List(), List(), List()
| 13: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@4c40b1b1), 4)
| |---> Deps: List((org.apache.spark.ShuffleDependency@55e610e3,12)) // constructed vertex cut
| |---> PrefLoc: List(), List(), List(), List()
| | 12: Serialized1x Replicated (partitioner: None, 0)
| | |---> Deps: List((org.apache.spark.OneToOneDependency@735ed323,2))
| | |---> PrefLoc: List(), List(), List(), List()
| | | 2: Memory Deserialized 1x Replicated (partitioner: None, 0) // cached to allow vertex extraction
| | | |---> Deps: List((org.apache.spark.OneToOneDependency@5677da01,1))
| | | |---> PrefLoc: List(), List(), List(), List()
| | | | 1: Serialized1x Replicated (partitioner: None, 0)
| | | | |---> Deps: List((org.apache.spark.OneToOneDependency@5689a400,0))
| | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | 0: Serialized1x Replicated (partitioner: None, 0)
| | | | | |---> Deps: List()
| | | | | |---> PrefLoc: WrappedArray(), WrappedArray(), WrappedArray(), WrappedArray()

vTable.index ------------------------------------
8: Memory Deserialized 1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
|---> Deps: List((org.apache.spark.OneToOneDependency@41f5ad2b,7))
|---> PrefLoc: List(), List(), List(), List()
| 7: Memory Deserialized 1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| |---> Deps: List((org.apache.spark.OneToOneDependency@683c03e1,6))
| |---> PrefLoc: List(), List(), List(), List()
| | 6: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| | |---> Deps: List((org.apache.spark.OneToOneDependency@3c22de3d,5))
| | |---> PrefLoc: List(), List(), List(), List()
| | | 5: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| | | |---> Deps: List((org.apache.spark.ShuffleDependency@152c95a3,4))
| | | |---> PrefLoc: List(), List(), List(), List()
| | | | 4: Serialized1x Replicated (partitioner: None, 0)
| | | | |---> Deps: List((org.apache.spark.OneToOneDependency@22140b31,3))
| | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | 3: Serialized1x Replicated (partitioner: None, 0)
| | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@51eacf71,2))
| | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | 2: Memory Deserialized 1x Replicated (partitioner: None, 0)
| | | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@5677da01,1))
| | | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | | 1: Serialized1x Replicated (partitioner: None, 0)
| | | | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@5689a400,0))
| | | | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | | | 0: Serialized1x Replicated (partitioner: None, 0)
| | | | | | | | |---> Deps: List()
| | | | | | | | |---> PrefLoc: WrappedArray(), WrappedArray(), WrappedArray(), WrappedArray()

vTable.values ------------------------------------
9: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
|---> Deps: List((org.apache.spark.OneToOneDependency@ed92dbb,7))
|---> PrefLoc: List(), List(), List(), List()
| 7: Memory Deserialized 1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| |---> Deps: List((org.apache.spark.OneToOneDependency@683c03e1,6))
| |---> PrefLoc: List(), List(), List(), List()
| | 6: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| | |---> Deps: List((org.apache.spark.OneToOneDependency@3c22de3d,5))
| | |---> PrefLoc: List(), List(), List(), List()
| | | 5: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| | | |---> Deps: List((org.apache.spark.ShuffleDependency@152c95a3,4))
| | | |---> PrefLoc: List(), List(), List(), List()
| | | | 4: Serialized1x Replicated (partitioner: None, 0)
| | | | |---> Deps: List((org.apache.spark.OneToOneDependency@22140b31,3))
| | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | 3: Serialized1x Replicated (partitioner: None, 0)
| | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@51eacf71,2))
| | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | 2: Memory Deserialized 1x Replicated (partitioner: None, 0)
| | | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@5677da01,1))
| | | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | | 1: Serialized1x Replicated (partitioner: None, 0)
| | | | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@5689a400,0))
| | | | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | | | 0: Serialized1x Replicated (partitioner: None, 0)
| | | | | | | | |---> Deps: List()
| | | | | | | | |---> PrefLoc: WrappedArray(), WrappedArray(), WrappedArray(), WrappedArray()

vTable ------------------------------------------
10: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
|---> Deps: List((org.apache.spark.OneToOneDependency@3eae0aae,8), (org.apache.spark.OneToOneDependency@143f45a8,9))
|---> PrefLoc: List(), List(), List(), List()
| vTable.index
|
| vTable.values
|

vid2pid -----------------------------------------
22: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
|---> Deps: List((org.apache.spark.OneToOneDependency@4320e76d,8), (org.apache.spark.OneToOneDependency@2539c789,21))
|---> PrefLoc: List(), List(), List(), List()
| vTable.index
|
| 21: Memory Deserialized 1x Replicated (partitioner: None, 0)
| |---> Deps: List((org.apache.spark.OneToOneDependency@745b0676,18))
| |---> PrefLoc: List(), List(), List(), List()
| | 18: Serialized1x Replicated (partitioner: None, 0)
| | |---> Deps: List((org.apache.spark.OneToOneDependency@7a6b2f03,8), (org.apache.spark.OneToOneDependency@12dbacbf,17))
| | |---> PrefLoc: List(), List(), List(), List()
| | | vTable.index
| | |
| | | 17: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| | | |---> Deps: List((org.apache.spark.ShuffleDependency@142a3945,16))
| | | |---> PrefLoc: List(), List(), List(), List()
| | | | 16: Serialized1x Replicated (partitioner: None, 0)
| | | | |---> Deps: List((org.apache.spark.OneToOneDependency@6015eb5a,15))
| | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | 15: Serialized1x Replicated (partitioner: None, 0)
| | | | | |---> Deps: List((org.apache.spark.OneToOneDependency@3f0e92fe,14))
| | | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | | eTable
| | | | | |

localVidMap -------------------------------------
24: Memory Deserialized 1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@4c40b1b1), 4)
|---> Deps: List((org.apache.spark.OneToOneDependency@55d48209,14))
|---> PrefLoc: List(), List(), List(), List()
| eTable
|

vTableReplicatedValues --------------------------
30: Memory Deserialized 1x Replicated (partitioner: None, 0)
|---> Deps: List((org.apache.spark.OneToOneDependency@72a548e4,24), (org.apache.spark.OneToOneDependency@4154ab89,29))
|---> PrefLoc: List(), List(), List(), List()
| localVidMap
|
| 29: Memory Deserialized 1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@4c40b1b1), 4)
| |---> Deps: List((org.apache.spark.ShuffleDependency@1dc9d0e1,28))
| |---> PrefLoc: List(), List(), List(), List()
| | 28: Serialized1x Replicated (partitioner: None, 0)
| | |---> Deps: List((org.apache.spark.OneToOneDependency@2cb0730e,26))
| | |---> PrefLoc: List(), List(), List(), List()
| | | 26: Serialized1x Replicated (partitioner: Some(org.apache.spark.HashPartitioner@523f6ca4), 4)
| | | |---> Deps: List((org.apache.spark.OneToOneDependency@7451b30d,8), (org.apache.spark.OneToOneDependency@1fc25624,25))
| | | |---> PrefLoc: List(), List(), List(), List()
| | | | vTable.index
| | | |
| | | | 25: Serialized1x Replicated (partitioner: None, 0)
| | | | |---> Deps: List((org.apache.spark.OneToOneDependency@fa565c6,9), (org.apache.spark.OneToOneDependency@33bcb230,21))
| | | | |---> PrefLoc: List(), List(), List(), List()
| | | | | vTable.values
| | | | |
| | | | | vid2pid.values
| | | | |

triplets ----------------------------------------
32: Serialized1x Replicated (partitioner: None, 0)
|---> Deps: List((org.apache.spark.OneToOneDependency@295687d9,24), (org.apache.spark.OneToOneDependency@6ff0ccc2,30), (org.apache.spark.OneToOneDependency@2a130df8,14))
|---> PrefLoc: List(), List(), List(), List()
| localVidMap
|
| vTableReplicatedValues
|
| eTable
|
Map(10 -> vTable, 24 -> localVidMap, 14 -> eTable, 21 -> vid2pid.values, 9 -> vTable.values, 22 -> vid2pid, 8 -> vTable.index, 30 -> vTableReplicatedValues)
````