# In-Memory Caching for Enhancing Subgraph Accessibility
## 1 Introduction  
Users have created and utilized a large amount of graph data due to the advancement of internet technology and mobile devices [1; 2]. Graph data have been utilized to represent interactions and relationships between objects through vertices and edges in various fields, such as social network service (SNS), semantic web, bio-information systems, and the Internet of Things (IoT) [3; 4; 5; 6]. These graph data are used in pattern mining, prediction, and recommendations through relationships between objects as well as the information of all vertices [7; 8; 9; 10; 11]. In social networks, graph data are used to determine user influence through human network analysis. In bio-information systems, graph data are utilized for disease diagnosis and new drug developments. E-commerce, such as online shopping and movie and music content services, employ graph data to recommend items to consumers. To process and analyze a large amount of graph data, various studies on distributed graph processing [12; 13; 14; 15], graph pattern matching [16; 17; 18], and incremental graph processing [19; 20; 21; 22] have been conducted. Recently, various studies on in-memory caching have been conducted to improvesystem performance effectively [23; 24; 25; 26; 27]. In-memory caching is a technique to reduce data access costs by loading some of the original data present on disk into memory. In-memory caching typically uses pre-fetching techniques to store data in memory that is expected to be used in the future since not all data can be loaded into memory. We use a replacement strategy to change cached data if there is not enough caching space allocated to memory. The graph expresses a complex relationship (multiple relationships) between objects through vertices and edges. Therefore, in applications such as SNS and the IoT, graph processing tends to approach associated subgraphs rather than accessing a single vertex or edge. In addition, when the size of the graph is large or the connection relationship of the graph is complicated, a situation occurs in which all of the subgraphs an individual wishes to cache are not loaded into memory. In order to reduce the cost of access to subgraphs, in-memory caching schemes are required, taking into account the characteristics of the use of the graphs. To do this, it is necessary to identify frequently used subgraph patterns and to load highly available subgraphs into memory. Caching neighboring subgraphs is necessary to reduce disk access costs because access to specific vertices in the process of query processing and analysis requires access to the subgraph connected to the edge. For the in-memory caching of graph data, the graph connectivity should be taken into consideration. A subgraph that is likely to be accessed spatially is predicted for future subgraph access considering connectivity. When a certain vertex is accessed, the neighbor vertices are likely to be accessed next through the edges connected to the vertex. The existing graph caching schemes have proposed a method that stored all neighbor vertices in the cache when accessing an arbitrary vertex [28; 29]. In [28], general Least Recently Used (LRU) was used as a graph replacement strategy, but the same processing method used for general objects was employed without consideration of the graph data topology. In [29], a replacement policy was proposed according to the topology characteristics of graph data. It cached the neighbor vertices of the accessed vertex since the neighbor vertices were likely to be used again in the future. It also proposed an algorithm that replaced a subgraph with a low weight with a new subgraph when the memory was full by assigning a weight during graph caching. However, subgraphs that were unlikely to be used later occupied the memory space by making all connected vertices memory resident when caching graph data. Thus, memory overload was likely to occur because all neighbor vertices were memory resident when accessing a vertex with many neighbors.