# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 4 Performance Evaluation  
In this study, the performance of the proposed continuous subgraph matching algorithm is compared with that of existing continuous subgraph matching algorithms. In terms of the environment for performance evaluation, an operating system with the specifications of Intel(R) Core(TM) i7-9700 CPU @ 3.6 GHz 64 bit was used. The maximum available memory was restricted to 1 GB. Python 3.6.8 was selected as the language to be used for the proposed scheme. Three data sets, wiki-Talk, cit-Patents, and YouTube, provided by SANP [25] were used in the performance evaluation. Table 2 shows the characteristics of the graphs used in the performance evaluation. Wiki-Talk indicates Wikipedia's communications network. Based on the contents of users' discussions, it displays information on users participating in discussions and articles upon which they developed discussions. Cit-Patents is a dataset of patents accumulated for 37 years in the United States. A graph was formed based on reference data in the cit-Patents dataset. As for the YouTube set, a community including the following three nodes was excluded. This set includes the graph data of communities including 13.5 or more nodes on average. This set includes information on approximately 8000 communities and shows a comparatively high clustering coefficient. Table 3 shows the parameters used in the performance evaluation. In this study, the performance of the proposed scheme was compared with that of an existing algorithm by adjusting the ratio of the used cache or prefetched catch to the entire cache space. To this end, the processing time was measured by changing the complexity of the query, the size of the window, and graph stream adjustment ratio. \(\alpha\) refers to the ratio of the used cache to the entire cache. If \(\alpha\) is 10, it indicates that the used cache accounts for 10% of the entire cache space and that the prefetched cache accounts for 90% of the entire cache space. To compare the data processing speed according to the complexity of the query, tests were conducted by varying a query as a simple query, complex vertex query, and complex vertex+edge query. Among the queries of interactive workload types provided by the LDBC (Linked Data Benchmark Council) [26], queries of a complex read-only query \begin{table}
\begin{tabular}{c c c} \hline \hline
**Dataset** & **\# of Vertices** & **\# of Edges** \\ \hline wiki-Talk & 2,394,385 & 5,021,410 \\ cit-Patents & 3,774,768 & 16,518,948 \\ YouTube & 1,134,890 & 2,987,624 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Sets of experimental data. Figure 9: Results of a sliding window (G\({}_{1}\)). type are used in this study. The queries of existing query types provided by the LDBC were defined as simple queries, and the queries including wildcard operations on vertices were defined as complex vertex queries. The queries including wildcard operations on vertices and edges were defined as complex vertex+edge queries. Moreover, tests were conducted by adjusting the size of the window from 100 to 1000 to measure the change in performance according to the size of the window. In each evaluation test, the size of the cache was adjusted from 0.1 to 1 kB to compare the performance according to the size of the cache. To measure the change in performance according to the graph stream adjustment ratio, tests were conducted by adjusting the graph stream adjustment ratio from 10% to 50%. Similarly, the size of the cache was adjusted from 0.1 to 1 kB in each evaluation test. Herein, the performance of the proposed scheme was compared with that of the existing scheme [20]. Since it is the subgraph matching scheme using the trie index, which is most similar to the proposed scheme among the existing schemes, it was selected as a comparison target. The existing scheme [20] efficiently performs continuous graph query processing based on a graph stream. An independent performance evaluation was conducted to determine the optimal cache replacement strategy and optimal cache space ratio.