# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
## 2 Related Work  
A materialized view is a database object that contains the results of a query and the query processing results. When a person conducts an operation, such as the aggregation or search of large-volume data, he or she may need to combine several tables to complete this operation. This type of complex operation may require a considerable amount of time for query processing. At this moment, a materialized view that stores query results in physical space can be implemented to reduce query processing loads. A general view maintains only query processing methods and does not generate practical query results. On the contrary, a materialized view contains practical query results in a table. That is, a general view is a logical table, whereas a materialized view is a table in physical space. A previous study developed a continuous subgraph matching algorithm based on a directed acyclic graph (DAG) to perform continuous subgraph matching in a real-time graph stream [17]. This algorithm converts a query graph to a DAG and detects a sink vertex that includes only ingoing edges in the converted DAG. Based on the detected sink vertex, it divides a query into subDAGs. Then, it detects a source vertex (root vertex) that includes only outgoing edges in each subDAG. Each source vertex sends a message to vertices that contain the same label values as those of a query, among the vertices connected to it. When a sink vertex receives a message from all the outgoing edges connected to it, the DAG-based continuous subgraph matching algorithm generates subgraph matching results. Subsequently, this algorithm performs final subgraph matching by combining the intermediate results of subDAGs. This algorithm uses Pregel, a graph distribution processing model, to transfer messages [21]. Pregel defines a function to be executed by a vertex in a graph, calls a function where all the vertices are user-defined in each superstep, and performs the next synchronization process in the order. Since a DAG-based continuous subgraph matching scheme uses Pregel, distributed processing is easy if a user defines only the functions to be performed by the vertex. However, these distributed systems must keep all data graphsin their memory when computing graphs. In addition, it is difficult to use in a limited memory environment because the messages necessary for communication between each node of the distributed server must be kept in the memory. Early continuous subgraph matching algorithms generated a redundant indexing cost when similar queries were registered. To solve this problem, a continuous subgraph matching algorithm based on a transition state was presented [19]. This algorithm defines a transition state of vertices in a record and records the state of vertices according to the occurrence of edges in a query graph. When all the vertices satisfy a certain transition state, this algorithm determines this state to be the final subgraph matching state. It uses a renewal-type graph that contains the vertices of a candidate query for the vertices of a data graph to store information on partial consistency with a query graph. This type of data-centric representation (DCG) is applied to maintain intermediate query results. When a graph stream is updated, information on consistency with a query graph is stored by an edge transition model by applying DCG. Each edge has a state among explicit, implicit, and null states. As for graph stream data, the transition state of vertices is stored according to query types. The state of an edge is stored as a null state when data that match with edge types do not exist. The state of an edge is stored as an implicit state when data match with the edge type of a query but do not match with the edge type of lower nodes. The state of an edge is stored as an explicit state when data match with both the edge types of a query and lower nodes.