# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 3 Proposed Continuous Subgraph Matching Scheme
### Cache Manager
As for statistical information on n6, the Statistics Manager records a load time as the current window time 1 and the size of intermediate results as 3. It also updates statistical information on n1 by applying the last hit time as 1, the number of hits as 1, and the number of joins as 1. When the size of the data to be loaded exceeds the size of the cache, cache replacement based on statistical information and a cache replacement strategy is performed. When graph data are input, the Query Processing Manager undergoes the FTV process based on trie indexing to implement query processing. To perform query processing efficiently, it uses intermediate results loaded in a cache. The Cache Manager uses the Statistics Manager to record the load time of a cache, the number of hits, the number of joins, and the size of intermediate results constantly. When the space of a cache is insufficient, the statistics-based cache replacement strategy is adopted to replace the data in a cache. When a cache of limited capacity becomes full of necessary subgraphs for query processing, the subgraphs stored in a cache should be replaced. At this time, the Cache Manager manages statistical data according to subgraph matching query processing and conducts a cache replacement based on the updated statistical information. Table 1 shows an example of a statistical table. ID is the unique number of a node, load time (LT) is the time of data loading, last hit (LH) is the last time a cache was hit, the number of hits (H) is the number of successful hits, the number of joins (J) is the number of successful join operations, the result size (S) is the scale of query results, and the query size (QS) is the scale of a query. Figure 5: Examples of cache data management. (**a**) Graph stream SW\({}_{1}\); (**b**) Graph stream SW\({}_{2}\). S is the sum of the size of all the intermediate results, and QS is the result of multiplying the number of vertices, edges, and unique labels included in a query. For example, the LT, LH, and H of the node 1 were 0, 50, and 100, respectively. The J, S, and QS of this node were 90, 100, and 20, respectively. For example, when the least recently used (LRU) policy is applied in a situation where two caches should be replaced, the results on node 1 and node 3 will be replaced. However, this decision leads to a situation where node 1 is replaced owing to a high hit rate and where node 5, whose H is only 1, is resident in a cache. Consequently, the efficiency of a cache is likely to decrease. To increase the efficiency of a cache, the following four cache replacement strategies are proposed herein based on statistical information: the popularity (POP); popularity and usage (POU); popularity, usage, and size (PUS); and popularity, usage, size, and query size (PUSQ) strategies. In this study, the table of statistical information indicated in Table 1 is used to select the targets to be replaced by the proposed strategies. The POP strategy replaces the low result of a node derived by dividing H by the time of residence of data in a cache as shown in Equation (1). Here, i is a trie index node stored in a cache, Hi is the number of hits, and Ai is the time of residence of data in a cache (current time-LT). The POU strategy replaces the low result of a node derived by multiplying the value obtained by the POP strategy by a ratio of joins (Ji/Hi), as shown in Equation (2). Ji is the number of join operations, and Hi is the number of hits. A large number of join operations compared with the hit rate indicates that join operations are likely to be performed for the next graph stream. In this regard, the POU value is calculated by considering this condition. The PUS strategy replaces the low result of a node derived by multiplying the value obtained by the POU strategy by a relative ratio of S (S/Smax). Here, Smax is the greatest result size and Si is the result size. In Table 1, the S (100) of Query 1 is Smax.