# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
###### Abstract  
With the expansion of the application range of big data and artificial intelligence technologies, graph data have been increasingly used to analyze the relationships among objects. With the advancement of network technology and the spread of social network services, there has been an increasing need for a continuous query processing algorithm that can manage large-volume graph streams generated in real time. In this paper, a sliding-window-based continuous subgraph matching algorithm that can efficiently control graph streams is proposed. The proposed scheme uses a query processing technique based on trie indexing. It establishes an index based on a materialized view of similar queries and conducts continuous query processing based on the materialized view to perform continuous query processing efficiently. It also provides wildcard operations on vertices and edges to consider various query types. Moreover, in this study, a two-level cache technique that can manage frequently used subgraphs and subgraphs that may be used in the future is developed, to handle intermediate query results in the form of a materialized view. Cache replacement techniques based on statistical data are also presented to improve the performance of the developed cache technique. The excellent performance of the proposed algorithm is verified by a conducting independent performance evaluation and comparative performance evaluation. continuous query processing; stream processing; graph stream; subgraph matching; materialized view +
Footnote †: journal: Medical  
a constant change in personal relationships among users. In social networking service environments, these users also create and share various types of documents. Consequently, the elements of graphs that are required for social network analysis are continuously altered. Researchers have used diverse graph analysis algorithms to extract significant information from graph streams that change in real time. Representative graph analysis algorithms include shortest path, PageRank, pattern analysis, frequent pattern detection, and subgraph matching algorithms [7; 8; 9; 10; 11; 12]. A subgraph matching algorithm identifies a similar subgraph to a query graph defined by the user in graph data [13]. This algorithm is used to find a subgraph that has a similar pattern to that of a query, among data graphs in numerous applications that deal with graphs, such as those of protein interaction networks and social networks [14; 15; 16; 17; 18; 19]. It is classified into two types: static subgraph matching algorithms [14; 15; 16], which perform subgraph matching based on large-volume graphs defined in advance, and continuous subgraph matching algorithms [17; 18; 19], which perform subgraph matching based on graphs that change constantly over time. A static subgraph matching algorithm generates a similar subgraph to a query as an outcome under the condition where the entire graph data are stored in advance. A continuous subgraph matching algorithm compares patterns of dynamically changing graph streams similar to those of queries based on a specific time interval in real time and generates adjusted results. As graph data have tended to be inputted in the form of streams in most recent applications, researchers have actively examined continuous query processing for real-time graph stream processing [17; 18; 19; 20]. The method in [17] based on Pregel enables users to perform distributed processing easily when they define a function to be executed by a vertex. However, this method has a problem in that all the graphs should be contained in the memory [18]. The method in [19] does not store the entire graph data but stores only information on the state of transfer of vertices and the occurrence of edges based on graph streams. However, as this method stores information on the state of transfer of vertices according to queries, it cannot handle similar queries at once. Moreover, it does not provide a parameter query as a query type, although it uses a data structure considering query types.