# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 3 Proposed Continuous Subgraph Matching Scheme
### Query Processing Manager  
The Query Processing Manager executes different processes according to the input types of stream data. If graph data is input, it analyzes if the graph data can be included in the query results managed by the current system. If the graph data can be included in the query results, it additionally generates query results. If a query graph is input, a query index is created according to the procedures described above. Figure 7 shows the procedures for query processing. When a query is requested, the Index Manager divides the query into max covering paths and creates a trie index based on each path of the query. The Query Processing Manager establishes a trie index by considering wildcard (var) operations on the query graph. In a trie, var vertices and edges are regarded and treated as nodes like vertices and indexes, including labels. When a graph stream is input after the establishment of a trie index, the stream processing module extracts a set (information on trie nodes) of candidates for subgraph matching based on the input stream. At this time, the Query Processing Manager inspects if the data of a set of candidates exist in a prefetched cache or a used cache prior to performing subgraph matching. If such data are not loaded in caches, the Cache Manager loads intermediate results on the parent and child nodes in a prefetched cache. The subgraph matching module performs subgraph matching based on  
Figure 6: Processing processes of cache replacement strategies. join operations by using intermediate query results loaded in a prefetched cache or a used cache. The Query Processing Manager responds to subgraph matching queries, whereas the Statistics Manager of the Cache Manager constantly records statistical information, such as the hit rate, the ratio of join operations, and the size of intermediate results. As for cache data, a TTL(Time-To-Live) value is determined based on statistics. After performing subgraph matching, the Query Processing Manager analyzes if the data exceeded the size of the cache. If the size of the cache is still sufficient, the Query Processing Manager outputs subgraph matching results. If the size of the cache is not sufficient, the Query Processing Manager replaces the data in the cache based on statistics and outputs subgraph matching results. Figure 8 shows the subgraph matching processes. The solid line indicates query processing, and the dotted line indicates cache data management. The first edge management process on a graph stream is marked in red, and the second edge management process is marked in blue. When the edges of graph data <0, 1, v1, v2, e1> are input, the edge indexing process is implemented to identify the list {Q1, Q2, Q5} of queries affected by edges. The reference indexing process determines the information on trie nodes, which indicates each query stored in a trie. For example, Q1 is {n3, n5, n6}. The trie indexing process detects the location of a trie node including the indexed information on current edges <v1, v2, e1> by performing trie node traversal according to queries. As for a specific example, the trie indexing process determines a trie {n1} practically affected by edges based on the result of trie node traversal on Q1. A join operation on the parent and child trie nodes of the corresponding node is conducted to generate intermediate node results in the form of a materialized view. The materialized view includes the unique numbers of nodes and vertices recorded. As n1 is a node of a current edge that serves as the root node, this node is regarded as query results. Thus, (n1, (0, 1)) is recorded in the result on the materialized view of n1. If the current cache does not include any data, the result of a join operation on a trie node n1 and its child trie nodes {n2, n4, n6} is not generated. The Query Processing Manager conducts subgraph matching by repeatedly applying the aforementioned processes to all the trie nodes included in a set of candidates.