## 3 Proposed Graph Compression Scheme
### Managing Pattern Dictionary  
All patterns are stored in an in-memory space called a dictionary; this process is performed using the graph pattern manager described in Section 3.2. The creation and management of the pattern dictionary are some of the main roles of the graph manager, and are accomplished through the pattern manager. The first step involves pruning using time stamps and the FP-tree. This process determines and manages the importance of patterns. The time stamp indicates the lifespan of each pattern, while the FP-tree is used to assess the importance of patterns. It maintains the top-K most frequently used patterns to limit the size of the pattern dictionary. Each reference pattern consists of a pattern ID, the pattern's time stamp, and scores assigned considering the pattern's size and frequency. Here, the RPS is used as an indicator of the pattern's importance. To effectively use provenance data, patterns extracted through graph pattern mining can use provenance information to track changes in the graph. Finally, the graph is transformed and stored through a dictionary encoding process. Figure 3 demonstrates how the graph pattern manager manages the pattern dictionary over time. Assuming a size of six for the pattern dictionary, during this process, patterns are stored in the pattern dictionary at each point in time, namely \(t1\), \(t2\), and \(t3\), and updated through the graph pattern manager whenever the pattern dictionary is refreshed. At \(t1\) and  
\(t2\), since the size of the pattern dictionary is larger than the number of existing patterns, new patterns can be added to the pattern dictionary. At \(t3\), no spare capacity exists in the pattern dictionary; therefore, patterns are deleted based on their scores. In Figure 3, the pattern with the lowest score, \(p1\), is deleted, and a new pattern, \(p7\), is added. The graph explorer performs the role of discerning the similarity between existing reference and new patterns. This includes the process of calculating the similarity between the reference and new patterns through subgraph isomorphism tests for each graph. Most existing studies determine reference patterns as graphs where vertices and edges commonly appear, and use a method to describe changes from the reference pattern in the pattern itself. However, if only perfectly matching graph patterns are searched for compression, then too few patterns would be available for compression, thus making it difficult to apply compression. Therefore, this study only performs comparative operations with patterns that are determined through the RPS value by the reference pattern generator and have a similarity level above a certain threshold, thereby reducing the overall computational cost. The graph pattern manager plays a crucial role in determining and managing the importance of patterns, using a pruning algorithm with time stamps and FP-tree, and limiting the size of the patterns stored in the pattern dictionary. These elements are combined to calculate the RPS, and patterns are kept in the dictionary in the order of their scores. Actual graph streams cannot always guarantee consistent patterns, as these may change over time. Considering these dynamic characteristics, this study sets a threshold \(\gamma\); if a specific pattern does not occur for a certain number of time windows matching this threshold, that pattern is deleted. This takes into account that the importance of patterns may change over time, removing older or less important patterns to enhance memory efficiency and focus more on the latest data. This process is defined as the time stamp trim process. Through this process, dynamic changes in graph stream data can be effectively reflected, and pattern dictionary management can be optimized to enhance the efficiency of real-time data processing. Graphs are constructed through several batch (\(B_{n}\)) processes. Each batch contains edge information, and this is combined for the value of the window to form the graph. The sizes of the batch and window are specified by the user.