# In-Memory Caching for Enhancing Subgraph Accessibility
## 2 Related Work  
The in-memory caching scheme has been utilized to process graphs fast in the distributed memory environment. [PERSON] et al. proposed a distributed in-memory graph storage system called NYNN to analyze large-scale graphs created in social networks [28]. This system took large-scale graphs, frequent access, and updates into consideration, which are the characteristics of a social network graph. They proposed a method that loaded the neighbors of an accessed subgraph into the memory for the first subgraph access to the subgraph used in arbitrary vertex access. The overall graphs are divided into subgraphs, which are then divided and stored as a form of data server. The information about the subgraphs and data server are stored and managed by the subgraph machine mapping table (SMMT) of the name server. It can reduce data I/O costs by prefetching subgraphs in advance. The first access to graph data is difficult to predict due to the access to the arbitrary vertex. However, the next access subgraphs are likely to be neighbor vertices on the basis of the previous requested vertex. Thus, the adjacent vertices of the requested vertex are all prefetched to the memory. [PERSON] et al. proposed a graph data caching policy for distributed graph processing on a big data platform [29]. This policy took metadata size, the number of hops between neighbors, and communication according to distributed processing into consideration by analyzing the graph data topology. It proposed a cache policy that cached neighbor vertices and vertices with multiple hops by estimating the neighbor vertices of the vertex currently accessed for the future access to graph data as a prefetching strategy. They also proposed clock-based graph-aware (CBGA) caching as a caching replacement strategy. The graph data caching policy proposed by [29] also caches neighbor vertices in the memory, the same as in [28]. In addition, not only single-hop neighbors but also multi-hop neighbor subgraphs are loaded to the memory. Whenever subgraphs are loaded to the memory, a TTL value is assigned to them. The TTL value is determined by the communication cost, the number of hops, and size. The TTL value decreases by one as time passes. Subgraphs whose TTL value becomes zero are removed from the memory. If there are no subgraphs whose TTL value is zero, the subgraphs with the lowest TTL value are removed from the memory first and new subgraphs are loaded. [PERSON] et al. proposed a semantic cache called GraphCache (GC) to reduce sub-iso testing in filter-then-verify (FTV) [23]. In GC, the cache manager consists of the cache stores and the window stores for subgraph and supergraph queries. The cache stores manage a component that stores copies of cached queries with their result sets, a combined index, and component storing statistics for each cached query. The combined index has a single index to expedite subgraph/supergraph matching of future queries against past queries and then provides lower disk space and I/O overhead. The window stores manage a component that stores new graph queries and their result sets and component storing statistics for each query in the previous component. GC was used to test various cache replacement strategies such as POP, PIN, and PINC, as well as LRU, where POP is popularity-based ranking, PIN is POP + number of sub-iso tests, and PINC is PIN + sub-iso test costs. [PERSON] et al. proposed a new caching scheme to reduce the computation and communication in a parallel breadth first search (BFS) [30]. This scheme caches the remote vertices previously visited and checks the cache to reduce communication. In the parallel BFS, many messages are sent to notify a process of different candidate parents for the same vertex. If the remote vertex is stored in the cache, it does not send a message, otherwise the cache is updated, and the message is sent. Each process maintains a vertex cache in memory. In the remote caching, each server process maintains the cache. Several servers are connected to the same switch to share a cache server.