# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 3 Proposed Continuous Subgraph Matching Scheme  
### Overall Structure  
In this paper, a continuous subgraph matching scheme that can solve the problems of existing continuous subgraph matching algorithms is proposed. In the proposed method, a query refers to a request for subgraph matching. When a graph stream is input, the proposed method performs a filter-then-verify (FTV) process based on trie indexing to respond to a query on continuous subgraph matching. It is more efficient to handle the same or similar queries at once than to handle each registered query in the process of managing queries on continuous subgraph matching based on a graph stream updated in real time. Hence, the proposed algorithm indexes a common pattern of queries by considering the redundancy of queries. It performs continuous subgraph matching by comparing a graph stream updated in real time with indexed queries. The intermediate query results should be contained in the memory and used owing to the characteristics of continuous query processing. To reuse intermediate query results efficiently, the proposed method generates intermediate query results in the form of a materialized view and manages these results based on a cache.  
Figure 1 shows the overall system structure of the proposed method, which consists of an Index Manager, Cache Manager, and Query Processing Manager. The Query Processing Manager comprises a stream processing module that performs graph stream processing and a subgraph matching module that performs subgraph matching in response to queries. The Index Manager conducts the process of indexing a query graph, called query indexing, in advance. Trie query indexing is applied to respond to multiple subgraph matching queries efficiently. The Query Processing Manager conducts continuous subgraph matching based on a graph stream updated in real time. The stream processing module extracts a set of candidates for subgraph matching based on a graph stream. This module uses existing intermediate results loaded in a cache to execute query processing efficiently. The subgraph matching module performs join operations by using a set of candidates for subgraph matching and the intermediate results loaded in a cache. Through join operations, a material view that represents intermediate results is generated. Based on the materialized view, the proposed method performs final subgraph matching. The Cache Manager conducts query processing based on a two-level caching technique and constantly records statistical data based on the Statistics Manager. When the space of a cache is insufficient, the statistics-based cache replacement strategies proposed herein are adopted to replace data in a cache.  
In this study, a graph is defined as G = (V, E, L(V), L(E)) where a direction and label are applied. V is a set of vertices, E is a set of edges, L(V) is a set of labels of vertices, and L\(\mathcal{E}\) is a set of labels of edges. Each vertex (v\(\in\)V) has a unique number (v\(\_\)id) and unique label (v\(\_\)label). Each edge (e\(\in\)E) is a pair of vertices (e = (s, t)). Here, s is a root vertex (source vertex), and t is an end vertex (target vertex). A query graph is defined as Q\({}_{\text{l}}\) = (VQ\({}_{\text{l}}\), EQ\({}_{\text{l}}\), L(V), L(E)). A graph stream is input based on the unit of a sliding window. It is assumed that a graph stream is input in the form of an edge stream (v\({}_{\text{1}}\)_id, v\({}_{\text{2}}\)_id, v\({}_{\text{1}}\)_label, v\({}_{\text{2}}\)_label, and e\(\_\)label, _t_). The unique numbers and labels of each vertex and the labels of each edge are input. Here, t refers to the time of generation of a graph stream.