# In-Memory Caching for Enhancing Subgraph Accessibility
## 3 The Proposed Graph Caching Scheme
### Cache Replacement
Thus, it showed a lower hit ratio than that of the proposed scheme due to frequent data replacement. The performance evaluation results showed that the hit ratio of the proposed scheme was increased approximately by 223% compared with that of NYNN, and 129% compared with that of CBGA on average. In order to show the superiority of the proposed method, we measured the query processing time according to the amount of data. The amount of data ranged from 1000 to 10,000, and the size of the cache was 2 GB. Figure 12 shows the evaluation results on processing time between the proposed and existing schemes. The proposed scheme showed better processing time compared with those of NYNN and CBGA. The two existing schemes cached all neighbors in the memory, and thus data I/O was frequent. However, since the proposed scheme cached top-k data only, it showed a smaller processing time than those of the existing schemes. The performance evaluation results showed that

Figure 11: Hit ratio on each of the datasets. Figure 10: Hit ratio of single and two-level caches. the processing time of the proposed scheme was improved on average by approximately 186% and 127% compared to those of NYNN and CBGA, respectively. The query processing time was measured on the basis of the cache size to show the superiority of the proposed method. The data used were the Twitter data, and the data were 5000 in number. The size of cache was changed from 256 MB to 2 GB. Figure 13 shows the query processing time according to memory size. When the cache size was 256 MB, the proposed scheme showed lower performance than the existing scheme. The proposed method occupies a certain amount of memory space because it maintains a query management table to detect subgraph usage patterns. Therefore, the cache is reduced, and this does not sufficiently store the subgraph to be cached. In addition, the proposed method manages the cache space divided into UC and PC, and thus if the cache space is small, the UC and PC sizes are relatively small. Therefore, processing performance is deteriorated because it cannot cache a highly usable subgraph. However, as the cache size increases, the performance of the proposed scheme is higher. Figure 12: Processing time according to data request. Figure 13: Processing time according to memory size. ## 5 Conclusions

In this paper, we proposed a two-level caching strategy that caches subgraphs that are likely to be accessed in consideration of the usage pattern of subgraphs to prevent the caching of low-usage subgraphs and frequent subgraph replacement in the memory. Since frequently used subgraphs are likely used again, we assigned higher weights to them and they were cached in the used cache. Furthermore, neighbor data of recently used data were cached in the PC since they were likely to be used again. This paper also conducted the management of cached data in each of the caches and performed data replacement between cached and new data when memory was full. The excellence of the proposed scheme was proven through performance comparison with the existing schemes. The performance evaluation results showed that the proposed scheme exhibited better performance in terms of hit ratio and data processing time than the existing schemes. Conceptualization, K.B., S.Y., D.C., J.L., and J.Y. ; methodology, K.B. and S.Y. ; software, S.Y. and J.L. ; validation, K.B., S.Y., and D.C.; formal analysis, K.B. and S.Y. ; writing--original draft preparation, K.B. and S.Y. ; writing--review and editing, J.Y. All authors have read and agreed to the published version of the manuscript. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (no. 2019R1A2C2084257, 2020R1F1A1075529); by the Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT (No.