# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 3 Proposed Continuous Subgraph Matching Scheme
### Cache Manager  
In this study, a two-level caching technique [24] is developed to perform continuous subgraph matching efficiently in a limited memory environment. The developed algorithm is applied to facilitate efficient subgraph query processing. Existing intermediate results stored in a cache are used to perform query processing efficiently. A used cache manages intermediate query results that are frequently used in query processing, and a prefetched cache manages intermediate query results that are likely to be used for the next query processing task. To apply [24] to this study, the trie indexing results and intermediate results were adjusted to be indexed. Accordingly, a prefetched cache was adjusted to manage the trie indexing results that are likely to be accessed. As for intermediate query results, information on the corresponding edges and information on results are separated for management. The information on edges includes the unique numbers of the corresponding edges recorded, whereas the information on results includes the unique numbers of join operation results. As the root trie node is regarded as results, both the information on edges and the information on results are updated to contain information on this node. When a target node is not the root trie node, the results on the current trie node are updated based  
Figure 4: Indexing of query graphs \(\mathrm{Q}_{1}\) to \(\mathrm{Q}_{5}\). Figure 3: Process of indexing a query graph \(\mathrm{Q}_{2}\). on the information on the edges of the target node, the results on the parent trie node, and the results of the join operation. Moreover, the results on the child trie node are repeatedly updated based on the results on the current trie node, the information on the edges of the child trie node, and the results of the join operation. Figure 5 shows the operation of the Cache Manager. Figure 5a is an example of the first window. When a graph stream <0, 1, v1, v2, e1, 1> is input, this stream is compared with the trie indexing results to determine a candidate set {n1} for subgraph matching. As the trie node n1 is the root node, a prefetched cache loads intermediate results on the child trie nodes {n2, n4, n6} of n1 for query processing. These results are not loaded in the current cache, which does not contain any data. In the subgraph matching process, the Cache Manager updates information on a used cache and relevant statistical information. The information on edges for a used cache includes the unique numbers of trie nodes and the unique numbers of the vertices of edges used for query processing. Consequently, (n1, (0, 1)) is recorded. As n1 is the root node, it is regarded as query results. Consequently, the result on n1 (0, 1) is applied as intermediate query results in the form of a materialized view. Statistical information comprises the unique number of a trie node, load time, last hit time, the number of hits, the number of joins, and the size of the intermediate result. As for statistical information on n1, the Statistics Manager records a load time as the current window time 1 and the size of intermediate results as 2. Figure 5b is an example of the second window. Like the processes described above, a candidate set {n6} is determined based on an input stream. To perform the processing of a trie node (n6) instead of the root node, intermediate results on the parent trie node (n1) and the child trie node (n8) in the form of a materialized view are loaded in a prefetched cache. A prefetched cache is used to load the data to be used for the next query processing in advance. Hence, when a used cache exists, it is instantly used. In (a), n1 is loaded in a cache while it is used for query processing. Hence, it is resident in a used cache. Then, subgraph matching based on the loaded data is conducted. The result on n6 (0, 1, 2) is updated as the intermediate result in the form of a materialized view based on the result on the parent trie node (n1) loaded in a cache and join operation results.