# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 4 Performance Evaluation
The relevant window processing time is presented according to a change in the \(\alpha\) value. The proposed algorithm derived the best window processing performance based on the wiki-Talk, cit-Patents, and YouTube datasets when the \(\alpha\) values were 40%, 10%, and 30%, respectively. In addition, the performance evaluation result showed a difference in the performance of a two-level cache system according to the datasets. Based on this result, it was analyzed that the cache space ratio should be adjusted to achieve the optimal query processing performance according to the characteristics of the datasets. In this study, the performance of the proposed continuous subgraph matching scheme was compared with that of an existing algorithm. To this end, the processing time required by both algorithms was compared by changing the complexity of the query, the size of the window, and graph stream adjustment ratio. Figure 13 shows the ratio of increase in the processing speed according to the complexity of the query. The processing time was measured by changing the queries to examine the change in performance according to the complexity of the query. The PUSQ strategy was adopted as a cache replacement strategy in this evaluation, and \(\alpha\) was established to derive the optimal performance according to the datasets. The graph adjustment ratio was established as 10%, and a single window included 100 edges. The processing time was measured based on 500 windows. The size of the cache was adjusted from 0.1 to 1 kB. The result processing time required by the existing algorithm was set as 100%, and the increase in processing speed was indicated as a percentage according to the size of the cache. The analytical result showed that the proposed scheme increased the average processing performance by 194% based on simple queries, by 193% based on complex vertex queries, and by 192% based on complex vertex + edge queries according to each dataset. Regardless of the query types, the redundancy of  
Figure 11: Hit rates according to the cache replacement strategies: (**a**) Wiki-Talk; (**b**) Cit-Patents; (**c**) YouTube. queries and caching techniques serve as the main factors affecting the increase in processing performance. The evaluation result showed that the size of the cache exerted a more significant effect on the query processing performance than the complexity of the query in a system environment with limited memory. The proposed scheme increased the processing speed by 189%, 194%, 195%, and 194% when the size of the cache was 0.1, 0.3, 0.5, and 1 kB, respectively. This result indicated that the processing speed did not increase in proportion to an increase in the size of the cache. In this regard, it is analyzed that more efficient query processing can be achieved through the selection of an appropriate cache capacity. As mentioned earlier, we presented an efficient way to process queries by caching only the necessary information without maintaining the overall index in the memory. The validity of the proposed two-level caching technique was proved through performance evaluation according to the cache size. Figure 14 shows the average window processing time according to the size of the window. The window processing time was measured based on simple queries by establishing the graph adjustment ratio as 10% and adjusting the size of the window from 100 to 1000. Accordingly, the size of the cache was adjusted from 0.1 to 1 kB during the evaluation. The evaluation result showed that the proposed scheme increased the average window processing performance by 35% to 85% according to the size of the cache compared with the existing algorithm. The proposed scheme showed a linear increase in the average window processing time when the size of the window increased. The existing algorithm, which does not use an additional cache, showed a geometrical increase in the window processing time when the size of the window increased.