## 3 Proposed Graph Compression Scheme
### Managing Pattern Dictionary
An example of graph and pattern creation is as follows. As shown in Figure 4, when \(\gamma=1\) and \(W_{batch}=3\), the window \(W_{0}\) consists of three batches as follows: \(W_{0}=\{B_{0},\ B_{1},\ B_{3}\}\). The pattern occurring at this point is shown at the top of the figure to be \(p1,\ p2,\ p3\), which represents the patterns of the graph entered up to that point. At the next point in time, \(W_{1}\), the pattern of the input graph is \(p2,\ p3,\ p4\). As time progresses from \(W_{0}\) to \(W_{1}\), pattern \(p1\) is not input; therefore,  
Figure 3: Example of pattern dictionary management by graph manager over time. the time stamp of that pattern is adjusted to \(T-n\), that is, \(T-1\). Here, when the number of consecutive time windows where a pattern does not appear exceeds the threshold \(\gamma\), that pattern is considered unimportant and removed. For instance, setting \(\gamma=1\) means a pattern will be discarded if it fails to appear even once. In the figure, because pattern \(p1\) is not input at the next time point \(W_{2}\), it is removed at time \(W_{2}\). Similarly, because pattern \(p4,\ p2\) is not input at the next time point, the time stamp value of that pattern is adjusted to \(T-1\). The proposed scheme applies the FP-Growth algorithm to the patterns stored in the dictionary to prune the infrequent patterns. This policy keeps the size of the pattern dictionary at a manageable level, maintaining only patterns appropriate for an in-memory environment. In other words, patterns with low usage are removed from the pattern dictionary, while those with high usage are updated to maintain the most current patterns; this enhances the compression efficiency in the dynamically changing graph stream environment. Figure 5 shows an example of the pruning process applied with the FP-Growth algorithm. The proposed scheme structures the vertices of the FP-tree as follows. \((P_{id},B,T,Frequency)W_{0}\). When the frequent threshold value is 3 and the time threshold value is 2, vertices in the FP-tree with a frequent value below the threshold are deemed not frequent patterns and removed. Thus, pattern \(P_{1}\), which does not meet the threshold in window \(W_{1}\), is removed. Additionally, patterns that do not meet the threshold in the window are also removed. This process reduces the storage cost of maintaining the patterns and secures space for new patterns to be added at the next point in time. Figure 6 shows the process of input patterns being stored in the pattern dictionary and information on each pattern. The pattern dictionary stores various pieces of information on each pattern, such as pattern ID, frequency, size, provenance, batch, and window. The reference pattern generator and graph manager use the content stored in the pattern dictionary to determine the reference pattern and decide which patterns to consider frequently occurring. A window consists of several batches. Figure 6 shows an example where a window is composed of three batches. Each batch involves the process of expanding the patterns stored in the pattern dictionary. That is, when performing three batches, the graph is composed of a total of four edges, which is the maximum number of batches + 1. Figure 4: Example of time stamp pruning with \(\gamma=1,\ Batch=3\). When the input graph is as shown on the left side in Figure 7, the initial form of the graph in the first batch is made up of single edges. These graphs are all of the same form, but are distinguished by the vertex labels. In the second batch, each pattern is expanded. Here, provenance allows for knowledge on how each pattern has been expanded using the previously existing data in the pattern dictionary. It writes all the updated information and patterns in pattern dictionary on a disk to maintain information related to all patterns. Utilizing this, the original data can be restored without any loss during graph compression and restoration. Figure 5: Pruning process applied with the FP-growth algorithm.