# In-Memory Caching for Enhancing Subgraph Accessibility
## 3 The Proposed Graph Caching Scheme
### Cache Replacement
Because vertices \(v_{2}\) and \(v_{3}\) are hit, as shown in Figure 7a, these vertices are deleted from the PC and are migrated to the UC. If the PC spaces are available due to the movement of \(v_{2}\) and \(v_{3}\), vertices \(v_{4}\) and \(v_{7}\) with the high frequent access pattern are prefetched to PC, as shown in Figure 7b. If the PC is full, the vertices are replaced by the FIFO, as shown in Figure 7c. ## 4 Performance Evaluation

The superior performance of the proposed scheme was proven through a performance evaluation comparison between the proposed and existing schemes. In this performance evaluation, we compared NYNN [28] and CBGA [29]. The performance evaluation environment is presented in Table 3. Simulations were conducted through the Java program on a personal computer running an Intel CoreTM i5-4460 CPU @ 3.20 GHz, RAM 8.00 GB, Microsoft Windows 10 64-bit operating system. For the experimental data, we used three datasets from Twitter [35], Weki-Talk [36], and YouTube [37], as presented in Table 4. The Twitter dataset was provided by Arizona State University, and the Weki-Talk and YouTube datasets were provided by Stanford University. The number of subgraphs requested ranged between 1000 and 10,000. Threshold \(\alpha\) should be determined to decide TTL value assigned from the UC proposed in this paper. The \(\alpha\) value that produced a high hit ratio was searched by changing the \(\alpha\) value that was multiplied by the number of vertices included in the pattern as well as the pattern weight in Equation (1). Performance evaluation was conducted by changing the \(\alpha\) value from 0.1 to 0.9 by 0.05 increments, when 5000 queries were generated. Figure 9 shows the evaluation results of hit ratio by changing \(\alpha\) value. As shown in Figure 9, the highest hit ratio was revealed when the \(\alpha\) value was 0.30. Thus, \(\alpha\) = 0.3 was used in performance evaluation because it showed the best hit ratio. Performance evaluation on hit ratio and processing time was conducted under three scenarios: when only the UC proposed in this paper was used, when only the PC was used, and when two-level cache was used. Here, 5000 queries were conducted with regard to Twitter, Weki-Talk, and YouTube datasets. For TTL weight, we used \(\alpha\) = 0.3 in the performance evaluation. Figure 10 shows hit ratio when each of the caches were used. The highest hit ratio was exhibited when, out of the three scenarios, two-level cache was used. When only the UC was used, frequently used subgraph patterns were cached in the memory, but overall performance was low because it did not take future access data into consideration. In contrast, when the PC was used, overall performance was also low because it did not take frequently used patterns into consideration, but instead only future access data were cached. The performance evaluation results showed that the hit ratio of the two-level cache was improved by 143% over the scheme using only UC, and 129% over the scheme using only PC. We evaluated the hit ratio to show the superiority of the proposed scheme for Twitter, Weki-Talk, and YouTube datasets. A total of 5000 queries were executed, and the size of the cache was 2 GB. Figure 11 shows the evaluation results on hit ratio using each dataset. The proposed scheme showed the best hit ratio compared to that of the existing schemes, NYNN and CBGA. NYNN did not consider the characteristics of the graph with respect to data replacement inside the memory, and thus the lowest hit ratio was revealed in the evaluation using overall datasets. Although CBGA considered \begin{table}
\begin{tabular}{c c c} \hline \hline
**Dataset** & **No. of Vertices** & **No. of Edges** \\ \hline Twitter & 11,316,811 & 85,331,846 \\ Weki-Talk & 2,394,385 & 5,021,410 \\ YouTube & 1,134,890 & 2,987,624 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Dataset. Figure 9: Hit ratio according to \(\alpha\) value. the graph characteristics, it did not assign a weight to hot data inside the memory.