# Efficient Continuous Subgraph Matching Scheme Based on Trie Indexing for Graph Stream Processing
###### Abstract
It does not present an additional caching technique either. The method in [20] efficiently performs multiple subgraph matching tasks by using trie indexing. This method stores the intermediate query results in the form of a materialized view, thereby facilitating swift query processing. However, it does not present a specific cache application measure. Existing studies assumed that all the intermediate results of indexing or query processing are resident in the memory. However, as a massive amount of graph data are generated in practical applications, the entire graph data are unlikely to be stored in a limited memory environment. To solve this problem, a method that can efficiently perform continuous subgraph query processing based on graph streams needs to be developed by considering a limited memory environment. In this paper, a sliding-window-based continuous subgraph matching scheme that can efficiently perform graph stream processing is proposed. The proposed scheme uses trie indexing, which can handle similar queries at once. The trie indexing technique integrates indexes for similar paths into a single index based on a principle that similar queries in a graph can be divided according to similar paths. Hence, this scheme is adopted in this study in continuous query processing. The proposed continuous subgraph matching algorithm also provides wildcard operations based on both vertices and edges to consider various query types. Accordingly, a statistics-based two-level caching technique that can efficiently manage intermediate query results renewed by graph streams is presented herein. This technique facilitates efficient continuous subgraph query processing by managing frequently used data at the top level and placing intermediate query results, which can be used for the following query processing, at the lower level. Furthermore, various cache replacement strategies are introduced to increase the efficiency of the existing trie indexing structure. This study has the following contributions:1. Trie-index-based similar query index management: Stream processing requires a quick response to queries because graph data is constantly entered. The proposed scheme improves the processing time of continuous queries by judging structurally similar graph queries as similar queries and managing similar queries with the trie index. 2. Support for various query types: The proposed scheme supports various types of graph queries. As in previous studies, it additionally supports wildcard operations as well as labels of vertices and edges. In the proposed study, wildcard means a query request that can be any label of the vertex or edge. Consideration of these wildcard operations was additionally made to manage the index of similar queries in the above-mentioned contribution. 3. Statistics-based two-level caching technique: The proposed study presents a statistics-based two-level caching technique to perform real-time stream processing. The proposed caching technique improves the query processing speed by caching data frequently used for query processing and data to be used for query processing in advance in-memory. The existing two-level caching technique proposed by this research team was modified to a form that can be applied to the trie index. In the real world, many queries can be registered and added continuously. If so, all indexes cannot be loaded into the memory, so the indexes must remain on the disk, and only the indexes currently required to process the query must be able to reside in the two-level cache. We verify the validity of the proposed statistics-based two-level caching technique through performance evaluations. The remainder of this paper is organized as follows. Section 2 reviews related previous studies and describes their limitations. Section 3 describes the details of the continuous subgraph matching algorithm proposed herein. Section 4 verifies the excellent performance of the proposed algorithm based on performance evaluation results.