## 3 Proposed Graph Compression Scheme  
### Overall Processing Procedure  
This study proposes a graph stream compression scheme based on a pattern dictionary using provenance. The proposed scheme selects sub-graph patterns with high influence in the graph as reference patterns, considering the relationship between each pattern and its sub-patterns during this process and assigning scores accordingly. Previous studies [13; 22] proposed schemes that offer high compression rates. However, they are not suitable for real-time data generation environments due to the significant amounts of time taken in the preprocessing stage to identify graph structures (star, clique, bipartite, etc.). Moreover, as the values being transformed increase, efficiency may decline compared with that when storing uncompressed data, and if specific graph structures are not found, the compression rate may decrease, leading to overall performance degradation. On the other hand, the scheme proposed in [19] selects common graphs that appear in both vertices and edges as reference patterns, and describes the changed parts in those patterns. However, this scheme is not suitable for stream environments, as it is constrained by the maximum size of graph patterns, and the pattern search time increases with the size of the patterns. Additionally, if a pattern completely different from the reference patterns appears, the applicable patterns may be limited or nonexistent, necessitating a re-search for patterns, which can cause a decrease in the compression rate. Other considerations exist when detecting frequent patterns in a graph stream and applying them to compression. First, efficiently using limited storage space while also performing rapid frequent pattern detection is necessary. In graph streams, data are continuously input and the analysis target data change in real time. Therefore, after a certain amount of data have been entered, it is necessary to delete data to free up memory for analyzing the next input data. Additionally, as the data that enter over time vary, the same patterns do not always appear, and they can change over time. Therefore, repeatedly verifying the isomorphism of the sub-graphs being compared for pattern detection is necessary. Typical subgraph isomorphism algorithms [3] involve finding patterns that match the graph's pattern perfectly; however, in this study, when graphs \(G_{1}\) and \(G_{2}\) exist, it means that the subgraph of \(G_{1}\) is isomorphic to that of \(G_{2}\). Therefore, patterns, such as \(G_{1}\in G_{2}\) are also considered isomorphic graphs. Lastly, when finding the pattern with the highest compression rate, considering time and frequency is crucial. This allows for the efficient application of frequent patterns to compression. Figure 1 illustrates the overall structure of the proposed incremental frequent pattern compression scheme. The detailed modules are described in the following section. The main modules include the reference pattern generator, graph manager, pattern dictionary, and compressor. The graph manager organizes raw data into graph form and delivers them to the reference pattern generator. It also assigns scores to the reference pattern candidates generated by the reference pattern generator, which is responsible for the initial step of finding patterns in each graph. The patterns identified here become reference pattern candidates and are sent to the graph manager. The pattern dictionary stores information on each pattern. The compressor performs the compression process. Figure 1: Overall structure of the proposed scheme. The main functions of the compressor are as follows: First, it manages the pattern dictionary while deleting unimportant patterns. During the deletion process, all patterns are written on a disk to prevent issues with decoding patterns used in previous compressions. The compressor divides the graph stream into fixed batch units for file management, and each compressed file includes a header specifying the patterns used in that file.