# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 3 Proposed Continuous Subgraph Matching Scheme
### Cache Manager
When a cache includes a considerable amount of intermediate query results, this algorithm is adopted to facilitate the maximum residence of the intermediate query results in the cache. The PUSQ strategy replaces the low result of a node derived by multiplying the value obtained by the PUS strategy by a relative ratio of QS (QS/QSmax), as shown in Equation (4). Here, QSmax is the highest QS, and QSi is QS. In Table 1, the QS (100) of Query 4 is QSmax. As indicated in the case of the PUS strategy, the PUSQ strategy facilitates the residence of data in a cache that shows high QS to increase the filtering effect. \[\text{POP}_{\text{i}}=\text{H}_{\text{i}}/\text{A}_{\text{i}}, \tag{1}\]  
\[\text{POU}_{\text{i}}=\text{POP}_{\text{i}}\times\text{J}_{\text{i}}/\text{ Hi}, \tag{2}\]  
\[\text{PUS}_{\text{i}}=\text{POU}_{\text{i}}\times\text{S}_{\text{i}}/\text{ Smax}, \tag{3}\]  
\[\text{PUSQ}_{\text{i}}=\text{PUS}_{\text{i}}\times\text{QS}_{\text{i}}/\text{ QS}_{\text{max}} \tag{4}\]  
Figure 6 shows the processes of the four cache replacement strategies developed in this study. The Statistics Manager applies each strategy based on the table of statistical information indicated in Table 1. If the POP strategy is applied for calculation under the assumption that the current time is 100, the scores for Nodes 1, 2, 3, 4, and 5 are calculated \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**ID**} & \multirow{2}{*}{\begin{tabular}{c} **Load Time** \\ **(LT)** \\ \end{tabular} } & \multirow{2}{*}{**Last Hit (LH)**} & \multirow{2}{*}{**\# of Hits (H)**} & \multirow{2}{*}{**\# of Joins (J)**} & \multirow{2}{*}{\
\begin{tabular}{c} **Result** \\ **Size (S)** \\ \end{tabular} } & \multirow{2}{*}{
\begin{tabular}{c} **Query Size** \\ **(QS)** \\ \end{tabular} } \\ \hline
1 & 0 & 50 & 100 & 90 & 100 & 20 \\
2 & 5 & 67 & 72 & 10 & 80 & 10 \\
3 & 10 & 60 & 63 & 23 & 30 & 70 \\
4 & 20 & 93 & 50 & 25 & 50 & 100 \\
5 & 99 & 100 & 1 & 1 & 10 & 10 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Table of cache statistics. to be 1, 0.75, 0.7, 0.625, and 1, respectively. Consequently, the POP strategy selects Nodes 3 and 4, which obtained the lowest scores, as the target nodes for replacement. At this time, Node 5's residence in the cache can decrease the efficiency of the cache. When the POU strategy is applied for calculation, Nodes 2 and 3 are selected as the target nodes for replacement. When the PUS algorithm is applied for calculation, Nodes 3 and 4 are selected as the target nodes for replacement. When the PUSQ strategy is applied for calculation, Nodes 2 and 5 are replaced. Through the aforementioned processes, Node 2, which shows a comparatively low efficiency for join operations, and Node 5, which shows a small size of intermediate results, are replaced in the cache. The Cache Manager performs subgraph matching on a graph stream and updates the cache and the Statistics Manager. Then, it applies each cache replacement strategy to the updated table of statistical information to calculate statistical values.