# In-Memory Caching for Enhancing Subgraph Accessibility
## 3 The Proposed Graph Caching Scheme
### Cache Replacement  
When the cache space is full, no more subgraphs are cached. Thus, a strategy that removes a subgraph from the memory or replaces a subgraph with a new subgraph is needed. The UC caches subgraphs that were used before. When a query request is received, the subgraphs are cached in the UC in case a cache miss or hit occurs in the PC. When the UC space is full, the UC replacement strategy is performed. Algorithm 2 shows the replacement algorithm of UC. We assume a new subgraph newSubgraph exists that we want to cache in UC when UC is full. Since UC is controlled by TTL values, we perform readTTL(0) to check the TTL values of each subgraph i cached in UC and newSubgraph. If the TTL of the newSubgraph is greater than the TTLs of the subgraphs cached in the UC, we replace the subgraph minSubgraph with the lowest TTL value with the newSubgraph. ```
Input newSubgraph: new subgraph ucSubgraph: subgraph cached in UC Output newSubgraph: subgraph changed by replacement in UC while(ucGraph) currentTTL \(\leftarrow\) readTTL(ucSubgraph, i) newTTL \(\leftarrow\) readTTL(newSubgraph) if currentTTL < newTTL tempList \(\leftarrow\) addtempList(i) if existtempList() minSubgraph \(\leftarrow\) findMinTTL(tempList) newSubgraph \(\leftarrow\) replaceSubgraph(tempList, minSubgraph)

Figure 5: Neighbor vertex caching according to graph query. Table 2 shows the UC replacement strategy. When vertices \(v_{1}\), \(v_{3}\), and \(v_{6}\) are requested as Figure 6, vertices \(v_{1}\) and \(v_{3}\) are hit so that the TTL values are updated and TTL values of other vertices are decreased. Furthermore, vertex \(v_{6}\) has a cache miss and is replaced with vertex \(v_{5}\), which has the lowest TTL value among the subgraphs in the cache. Thus, vertex \(v_{5}\) is deleted and vertex \(v_{6}\) is stored. When a query request is received, since the neighbor vertices of the used vertex are likely to be used next time, the PC caches the neighbor vertices of the used subgraph. The PC manages the cached subgraph according to the FIFO method. Algorithm 3 shows the PC replacement algorithm. The cache replacement in PC occurs when a cache hit occurs in the PC and the subgraph cached in the PC moves to the UC, and when a new graph newSubgraph is requested and requires caching neighboring subgraphs. If the cache hit is a cached subgraph in the PC, resultGraph is generated. Therefore, to replace the cached subgraph in the PC, the resultGraph is determined to exist. If resultGraph exists, we first move the hit subgraph from the PC to the UC by performing moveUC() and perform the readSubgraph() to store the neighboring subgraphs connected to the newSubgraph in the PC. If there is no cache hit in the PC but there is a request for newSubgraph, we delete the existing subgraph by performing deleteSubgraph() and store the new subgraph by performing addSubgraph(). ```
Input  newSubgraph: new subgraph  resultGraph: results hit by rsubGraph on PC  pcSubgraph: subgraph cached in PC Output  newpcSubgraph: subgraph changed by replacement in PC if existresultGraph(resultGraph)  moveUC(resultGraph)  tempSubgraph \(\leftarrow\) readSubgraph(newSubgraph)  newpcSubgraph \(\leftarrow\) newpcSubgraphaddPC(tempSubgraph) else  newpcSubgraph \(\leftarrow\) deleteSubgraph(pcSubgraph)  tempSubgraph \(\leftarrow\) readSubgraph(newSubgraph)  newpcSubgraph \(\leftarrow\) addSubgraph(tempSubgraph)
``` \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**VID** & \(v_{1}\) & \(v_{2}\) & \(v_{3}\) & \(v_{4}\) & \(v_{5}\) & \(v_{6}\) \\ \hline Initial TTL & 10 & 3.5 & 15 & 21 & 5 & - \\ Updated TTL & 27 & 34 & 30 & 20 & 4 & - \\ Final TTL & 27 & 34 & 30 & 20 & - & 17 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Example of UC replacement. Figure 6: New requested query in UC. Figure 7 shows the PC replacement strategy. We suppose that a new query is requested as shown in Figure 8 when a vertex \(v_{1}\) is stored in the PC and vertices \(v_{2}\) and \(v_{3}\) are stored in the UC.