## 4 Discussions of Two Graph Models  
Although _SCSG_ and _DCSG_ graphs both represent the sharing between files, they are different in many aspects. In this section, we describe the two primary differences of these two graph models.  
First, compared with _DCSG_, _SCSG_ graphs have less vertices and edges, so _SCSG_ graphs consume less RAM and storage space than _DCSG_ graphs. For example, for the small sample shown in Table 1, the _SCSG_ graphs shown in Figure 2 and Figure 3 both have 19 vertices and 19 edges. In comparison, the _DCSG_ graph shown in Figure 4 has in total 57 vertices (19 _File_ vertices and 38 _Chunk_ vertices), and 184 edges. Even if optimizations such as merging adjacent shared chunks can attenuate the space consumption of _DCSG_ graphs (see Section 3.3 for details), _DCSG_ graphs in general consume more RAM or storage space than _SCSG_ graphs. According to Table 5, with both optimizations, for _WL1_, the _DCSG_ graph has 337,602 vertices (162,779 file vertices and 174,823 sub-file vertices) and 1,034,923 edges. Conversely, the _SCSG_ graph can be 162,779 file vertices and up to 162,778 edges, which are far less than the _DCSG_ graph. For this reason, _SCSG_ graphs are more scalable than _DCSG_ graphs to represent the same set of deduplicated files.  
Second, _DCSG_ graphs are more accurate to some manipulation operations than _SCSG_ graphs. Such operations included the selection of a sub-graph (including both vertices and edges) from a whole graph, as well as the dynamic modifications of shared content that may end up changing the graph itself. After  
Figure 14: _Cont._  
these manipulation operations, _SCSG_ graphs may not reflect the accurate sharing, while _DCSG_ graphs reflect the sharing properly. One example of this inaccuracy is the size computation. For _SCSG_ graphs, recall the size of a graph is computed by summarizing all vertex weights and then subtracting all edge weights in the graph (due to deduplication), but after partitioning, the size computed in this way is an upper bound of the actual deduplicated size. Take the sample shown in Table 1 for example, if we partition the _SCSG_ graph with a STAR connection topology in Figure 2 into two sub-graphs G1 and G2, we have \(G1=\{v1,v15,\ldots,v19\}\) and \(G2=\{v2,\ldots,v14\}\). Based on graphs of G1 and G2, the deduplicated size of G1 is 164 bytes, and the deduplicated size of G2 is 592 bytes. However, in reality, the deduplicated size of G1 is 100 bytes, and the deduplicated size of G2 is 128 bytes. Therefore, after partitioning, the deduplicated size of the sub-graph is not accurate, but an estimate. Note that the estimate is always an upper bound of the actual deduplicated size because in _SCSG_ graphs, edges are sparse and the sub-graph may miss some edges after manipulation. In this example, for G2, v13 and v14 share 16 bytes, but there is no edge connecting v13 and v14 due to the sparseness of edges. Using the same subgraphs G1 and G2 in the _SCSG_ graph using the CHAIN connection topology in Figure 3 however, the size estimation is perfect, the deduplicated size of G1 is 100 bytes, and the deduplicated size of G2 is 128 bytes. We could conclude from this made-up experiment that CHAIN connection topology gives much better subgraph size estimate than the STAR connection topology for _SCSG_ graphs. This is not the case on large scale realistic workloads as we have shown, one reason being that k-cores are not made up of randomly selected vertices. For _DCSG_ graph as shown in Figure 4, for the same two subgraphs, the deduplicated size of G1/G2 can be computed by adding the sizes of all unique chunks in the sub-graph, so the deduplicated size of G1 or G2 is accurate. Indeed, for _DCSG_ graphs even for random subgraphs the deduplicated size computation is still accurate (and not an upper bound as for _SCSG_ graphs).