# In-Memory Caching for Enhancing Subgraph Accessibility
## 3 The Proposed Graph Caching Scheme  
### Overall Structure  
Graph data are processed rapidly by prefetching subgraphs on a disk to the memory in advance. The existing studies did not consider neighbor vertices employed together when subgraphs were used during graph data processing. Moreover, when subgraphs were cached in the memory, the neighbor vertices were all cached. Thus, this paper proposes a two-level caching scheme that considers the usage pattern and access frequency of subgraphs. The proposed scheme is configured with a two-levelcaching structure managed by different caches by caching the frequently used subgraphs and neighbor vertices of the accessed subgraph. Figure 1 shows the proposed overall structure. The structure of the proposed in-memory caching scheme is divided into a cache manager and a two-level cache. The cache manager stores query histories used in the query management table and generates frequent subgraph patterns through an FP-tree. In addition, it generates a subgraph access pattern and assigns a TTL value for managing cached graphs. The two-level cache is divided into a used cache (UC) and a prefetched cache (PC). In the used cache, subgraphs that are likely to be used among previously used subgraphs are cached. In the PC, unused subgraphs that are likely to be used in the next query are cached. If subgraphs stored in the cache are actually used, they are migrated to the used cache. Graph \(G=(V,E)\) is represented as a set of vertices \(V\) and a set of edges \(E\). Vertex \(V\) consists of \((VID,VP)\), where \(VID\) is the vertex identifier and \(VP\) represents the type or label, etc. as the attribute information of the vertex. Edge \(E\) consists of \((EID,EP)\), where \(EID\) is the edge identifier, and \(EP\) value represents the edge weight and type, etc. The graph is implemented as an adjacency list consisting of a vertex table and an edge list [33; 34]. The vertex table manages information about all vertices and keeps pointers to \(VID\)s, attributes, and edge lists connected to vertices for each element. The edge list is implemented as a link list and maintains the vertices connected to the EID, attributes, and vertices for each element. Since UC and PC are given TTL values, they are implemented as ordered linked lists according to TTL values. Since PC is managed by FIFO structure, they are implemented as queues implemented by linked lists. When a graph request is received, the system inspects whether the requested subgraphs are cached in the UC or the PC. If subgraphs are found, subgraphs inside the memory are used. Otherwise, subgraphs are loaded from the disk. Not only replying to the query, but also storing the requested query in the query history management table is performed at the same time. The FP-tree is created through the query history management table, and the TTL value is calculated through the query pattern, thereby assigning the TTL value to the subgraph stored in the used cache. Algorithm 1 shows  
Figure 1: Overall structure. the subgraph access process. When there is a request for a subgraph, we first determine whether the requested subgraph rsubGraph exists in memory. If rsubGraph exists in memory, the requested subgraph is passed on to resultGraph via readSubgraph(). Otherwise, we determine whether a cached subgraph exists in UC or PC. If rsubGraph exists in UC or PC, we forward the requested subgraph to resultGraph. If rsubGraph exists in UC, we increase the TTL value to keep the corresponding subgraph constant, otherwise we decrease the TTL value. If rsubGraph does not exist in UC and PC, we load the subgraph into memory by performing loadSubgraph().