## 3 Use Cases of Graphs
### The Naive Algorithm
In the first step, all \(S\) selected \(FID\)s and their adjacency lists are fetched from the \(FID\) list to form a _DCSG_ graph, denoted as _B-Graph_. The total size of all \(FID\)s are computed, denoted as \(T_{files}\). The \(FID\) vertex list is implemented as a list, while the \(CID\) vertex list is implemented as a hash table to speed up the lookup performance. In the second step, a breadth-first search (BFS) finds out all \(CID\)s whose degrees are larger than 1, where per-\(CID\) degrees are also recorded. We denote the set of these \(CID\)s as \(S_{CID}\). Each \(CID\) in \(S_{CID}\) has their redundant duplicate size as \(RedundantDupSize=(degree-1)*ChunkSize\), and the sum of all redundant duplicate sizes are recorded as \(T_{dup}\). The accurate deduplicated size of \(S\) files is \(T_{dedup}=T_{files}-T_{dup}\). Figure 13 show an example of the _Graph_ algorithm. Initially, each file has a mapping to all its chunks. Each file has its own file size. Each chunk size is 1 so that the edge weight is 1. Chunk identifiers are the result of deduplication so that 2 files can map to the same chunk identifier. For example, \(C2\) appears in file \(F1\), \(F2\) and \(F6\). If \(F2\), \(F5\) and \(F6\) are chosen as the subset of files, in Step 1, these 3 files and its chunks form a _B-Graph_, \(F2\), \(F5\) and \(F6\) have their file sizes as 5, 4 and 8, respectively. In Step 2,  
all chunks are traversed to find out those chunks with more than 1 edge, \(C2\) and \(C6\) are chosen. The accurate deduplicated size of the subset is \(T_{files}-T_{dup}=(5+4+8)-(1+2)=14\). The asymptotic complexity of the _Graph_ algorithm is \(O(S+C)\) since step 1 needs to choose \(S\) files and step 2 needs to scan \(C\) chunks. The Optimized Graph Algorithm  
The _Graph_ algorithm is not scalable with the number of files (and the number of chunks for these files), we propose three optimizations to mitigate the scalability concern. We denote the algorithm with these three optimizations as _GraphOpt_. The first optimization (_OPT-1_) is to reduce the number of files and chunks represented in the graph. Note that not all chunks are shared among files, and some files do not share any chunks with other files. These chunks and files do not lead to the inaccuracy of the size computation. We can safely remove them from the graph representation. As shown in Table 5, for _WL1_, this optimization can reduce the number of \(FIDs\) to 56% (\(\frac{162,779}{289,295}\) of the original, and the number of \(CID\)s to 8.4% (\(\frac{1,475,780}{17,509,025}\)) of the original. For _WL2_, with this optimization, the number of \(FID\)s drops to 27% (\(\frac{55,455}{201,406}\)) of the original, and the number of \(CID\)s drops to 2% (\(\frac{237,235}{12,021,126}\)) of the original. The second optimization (_OPT-2_) is to aggregate adjacent shared chunks into 1 shared _segment_ to further reduce the number of vertices. The idea behind this optimization is that sharing chunks between two files consists of sequences typically larger than 1 chunk in deduplicated storage systems [12, 13]. We define a _segment_ as a range of inter-file shared chunks that appear adjacently and in the same order in all files sharing them. _GraphOpt_ has 2 steps to identify _segments_. In the first step, each file deduplicates with itself to remove intra-file duplicates, where only the first occurrences of intra-file duplicate chunks are kept. In the second step, _GraphOpt_ employs a straightforward linear algorithm to identify segments. Although more advanced algorithms can be used, such as those based on suffix array [12, 14], we  
Figure 13: An example of the _Graph_ algorithm. “Initial State” shows the initial state of the metadata, “Step 1” shows the resulting _B-Graph_ of step 1, “Step 2” shows the computation result. (**a**) Initial State; (**b**) Step 1; (**c**) Step 2.  
developed a straightforward algorithm since the identification of segments occurs only once from the original deduplication metadata.