# In-Memory Caching for Enhancing Subgraph Accessibility
## 3 The Proposed Graph Caching Scheme
### Subgraph Caching  
We present a cache structure that divides a cache level into a UC and a PC to efficiently access subgraphs that were used frequently and subgraphs that are likely to be used in the future, which are managed differently. Since the criteria of loading subgraphs to the memory differ for the two levels, we stored subgraphs in different caches according to the criteria to manage subgraphs easily. When a graph query is requested, previously used subgraphs are likely to be used again. Thus, the UC caches the used subgraphs and stores subgraphs used frequently in the memory for a long period of time. If the cache space with a limited size is full, the cached subgraph must be replaced. When the UC space is full, the UC replaces the subgraph according to the TTL value. If the number of vertices included in the subgraph is high, it is likely that the vertices used in other queries will be included. In addition, the subgraphs frequently used in past queries are likely to be used in the future. Therefore, the TTL value for a subgraph depends on the number of vertices contained in the subgraph and the frequency of use of the subgraph. Here, \(NV_{i}\) is the number of vertices included in the subgraph and \(PW_{i}\) is the pattern weight given in the process of detecting frequent patterns through the FP-tree as the usage pattern on the subgraph. Subgraphs with large TTL values are less likely to be replaced. Cached subgraphs may differ in the importance of the number of vertices and frequency of use, depending on application. Equation (1) uses \(\alpha\) to assign weights to the number of vertices and pattern weight. Here, \(\alpha\) ranges from 1 to 1. \[TTL_{i}=\alpha NV_{i}+(1-\alpha)PW_{i} \tag{1}\]  
Figure 4 shows the subgraph patterns used by three queries: \(Q_{1}\), \(Q_{2}\), and \(Q_{3}\). If we detect a frequent pattern by constructing an FP-tree for the subgraph used by each query, we can see that \(G_{1}\) with vertices \(v_{1}\), \(v_{2}\), and \(v_{3}\) is frequently generated by the frequent pattern. When queries \(Q_{1}\), \(Q_{2}\), and \(Q_{3}\) are received, the vertices in each query are cached in the UC. Table 1 presents the TTL values, where VID is a vertex identifier and TTL is a TTL value assigned to each vertex. Each subgraph calculates a TTL value using Equation (1) and assigns the calculated TTL value to each information  
Figure 3: Query history and FP-tree: (**a**) query history management table; (**b**) FP-tree. contained in the subgraph. The TTL values of vertices \(v_{1}\), \(v_{2}\), and \(v_{3}\) are high because they belong to \(G_{1}\), which has a high access pattern. Query processing and analysis of graphs perform operations with neighboring vertices connected by edges incident to a particular vertex. In other words, since the graph computation is done using the relationship between vertices, it is not performed using only one vertex or edge, but also uses the other vertices associated with a particular vertex. Therefore, when we approach a particular vertex, we approach the vertices adjacent to it. The neighbor vertices of the requested subgraph are cached in the PC. The number of subgraph accesses that were used together is stored in each graph edge. For example, if vertex \(v_{1}\) is used along with vertex \(v_{2}\), the number of accesses of the edge that connects vertices \(v_{1}\) and \(v_{2}\) is increased by 1. If the graph is complex and there are too many vertices adjacent to a particular vertex, all neighbors of the particular vertex cannot be stored in a cache space with a limited size. Therefore, when approaching a particular vertex, it selectively caches neighboring vertices in consideration of accessibility. When a query is requested, the neighbor vertices of the used subgraph that have a high frequency access pattern are also cached along with the used memory in the memory. Top-k vertices that have a high access pattern are singled out using the number of accesses stored in