# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 4 Performance Evaluation
Specifically, the window processing time required by the proposed cache replacement strategies was compared with that required by existing cache replacement strategies. The hit rate was measured according to the cache replacement strategies to identify the optimal cache replacement strategy. Moreover, the window processing time was compared according to the ratio of use of a two-level cache system. Figure 10 shows the average window processing time according to the cache replacement strategies when the size of the cache was established as 0.1 kB. A single window consisted of 100 edges and the average window processing time based on 500 windows was measured according to the datasets. With regard to cache replacement strategies, the proposed strategies (POP, POU, PUS, and PUSQ strategies) were compared with general strategies (LRU, first-in first-out (FIFO), and least frequently used (LFU) algorithms). When the proposed cache replacement strategies were applied to the wiki-Talk dataset, the average window processing time was 29.7 ms. This result confirmed that the proposed strategies increased the window processing performance by 182% compared with existing cache replacement strategies. When the proposed strategies were applied to the cit-Patents dataset, the window processing performance increased by 163%. When the proposed strategies were applied to the YouTube dataset, the window processing performance increased by 170%. Based on the measurement results, the proposed cache replacement strategies increased the window processing performance by 171% on average compared with existing algorithms. In terms of datasets, the PUSQ strategy derived the best performance for the processing of the wiki-Talk and YouTube datasets. The POP strategy derived the best performance for the processing of the cit-Patents dataset. This result indicates that the use of an appropriate cache replacement strategy for data characteristics can lead to efficient cache replacement. \begin{table}
\begin{tabular}{c c} \hline
**Name** & **Value** \\ \hline \# of window size (\# of vertices) & 100, 300, 500, 1000 \\ Cache Size(kB) & 0.1, 0.3, 0.5, 1 \\ \(\alpha\) (\%) & 10, 20, 30, 40, 50, 60, 70, 80, 90 \\ Graph Modification Ratio (\%) & 10, 20, 30, 50 \\ \hline \end{tabular}
\end{table} 
Table 3: Parameters for the performance evaluation. Figure 11 shows the hit rate according to the cache replacement strategies when the size of the cache was established as 0.1 kB. A single window includes 100 edges, and an analysis of the hit rate based on 100 windows was conducted. The analytical result based on the wiki-Talk dataset showed that the PUSQ strategy derived the highest hit rate of 70.29%. The hit rates for the used cache and prefetched cache were 43.25% and 27.04%, respectively. The analytical result based on the cit-Patents dataset showed that the POP strategy derived the highest hit rate of 66.28%. The hit rates for the used cache and prefetched cache were 27.99% and 38.30%, respectively. The analytical result based on the YouTube dataset showed that the PUSQ strategy derived the highest hit rate of 67.90%. The hit rates for the used cache and prefetched cache were 43.93% and 23.98%, respectively. As the PUSQ strategy derived the best performance on average, in this study, this algorithm is established as the main cache replacement strategy to be used to compare the performance of the proposed continuous subgraph matching scheme with that of the existing algorithm. Figure 10: Average window processing time according to cache replacement strategies. Figure 11: _Cont._  
Figure 12 shows the stream processing time as compared to the worst performance derived from the PUSQ cache replacement strategy according to different cache space ratios when the size of the cache was 0.1 kB. A single window contained 100 edges, and the processing time was measured based on 500 windows. The longest window processing time was required when \(\alpha\) was 90%. Hence, the window processing time was established as 100% when \(\alpha\) was 90%.