## 3 Use Cases of Graphs
### The Naive Algorithm
The basic idea behind the straightforward linear algorithm is that segments are identified by two factors, repetition and adjacency. The repetition counter increases when there is a hash value match from inter-file duplicate. The adjacency means that a sequence of chunks with the same repetition are adjacent in all files sharing them. Therefore, any neighboring chunks that do not have the same repetition or are not adjacent in files are not in the same segment, and one can mark the boundary of segments accordingly. For this reason, there are two scans. In the first scan, the boundaries of segments are marked in the array of unique chunks by scanning all chunks from all files. We need an auxiliary data structure to remember the unique chunks and to query the scanned chunks, and we choose a hash table as the auxiliary data structure. With the help of the hash table, we can have an array of unique chunks, upon which we can mark the boundaries of segments. In the second scan, segments are identified by following the marks determined in the first scan. As shown in Table 5, after applying the first two optimizations, the number of edges drops to 6%-7% of the original number of edges (\(\frac{1.034,923}{17,509,025}=6\%\) for WL1 and \(\frac{810,264}{12,021,126}=7\%\) for WL2), the number of sub-file vertices drops to less than 1% of the original (\(\frac{174,823}{17,509,025}=0.99\%\) for WL1 and \(\frac{76,772}{12,021,126}=0.66\%\) for WL2). The reduction of both edges and sub-file vertices greatly improves the scalability of the _DCSG_ graph. For example, for a 1 PB deduplicated storage system, if the characteristics of files (e.g., file sizes, chunk sizes) and their sharing are similar, there will be \(\frac{1000 TB}{3 TB}\cdot 1034923=333M\) edges and \(\frac{1000 TB}{3 TB}\cdot 174823=58.3M\) sub-file vertices, which are reasonable numbers to work with. The third optimization is to make the calculation more stream-friendly. Instead of loading the whole graph into RAM, one can scan shared chunks from selected files one by one. For each new file, the file size after intra-file deduplication is added to \(T_{files}\). For each chunk that is already in the \(CID\) hash table, \(T_{files}\gets T_{files}-T_{CID}\), where \(T_{CID}\) is the size of the chunk. If the chunk is not in the \(CID\) hash table, it is inserted into the \(CID\) hash table. With this optimization, we do not need to keep the whole graph in RAM. Instead, we only needs to keep the hash table keyed by \(CID\)s in RAM. \begin{table}
\begin{tabular}{l r r} \hline \hline
**Workload** & **WL1** & **WL2** \\ \hline Num. of File Vertices & \(289,295\) & \(201,406\) \\ Num. of Sub-File Vertices & \(17,509,025\) & \(12,021,126\) \\ Num. of Edges & \(17,509,025\) & \(12,021,126\) \\ Num. of File Vertices with OPT-1 & \(162,779\) & \(55,455\) \\ Num. of Sub-File Vertices with OPT-1 & \(1,475,780\) & \(237,235\) \\ Num. of Edges with OPT-1 & \(8,160,786\) & \(3,961,316\) \\ Num. of File Vertices with OPT-1,2 & \(162,779\) & \(55,455\) \\ Num. of Sub-File Vertices with OPT-1,2 & \(174,823\) & \(76,772\) \\ Num. of Edges with OPT-1,2 & \(1,034,923\) & \(810,264\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Graph characteristics after applying optimization 1 and 2 in _GraphOpt_ for two workloads. Results  
In this section, we show the effectiveness of _GraphOpt_ by comparing it with _Naive_ and _Graph_ algorithms. For all three algorithms, the database or graph is assumed to be not cached in RAM initially, and they are stored on external hard drives. At the computation time, the graph or database needs to be loaded into RAM, where RAM is configured to be 1 GB for both graph-based algorithms (_i.e._, _Graph_ and _GraphOpt_) and the database-based algorithm (_i.e._, _Naive_). For _Naive_ algorithms, we used a commercial database implementation [15] to run the SQL queries. We configured 1 GB for the buffer cache of the database, and we made a fair comparison by tuning the database properly to have a reasonable performance.