_applied sciences_  
_Article_  
**Graph Stream Compression Scheme Based on Pattern Dictionary Using Provenance**  
**[PERSON] 1\({}^{\text{\textregistered}}\)**, **[PERSON] 1, [PERSON] 2\({}^{\text{\textregistered}}\)**, **[PERSON] 1\({}^{\text{\textregistered}}\)**, **[PERSON] 3\({}^{\text{\textregistered}}\)** and **[PERSON] 1\({}^{\text{\textregistered},\bullet}\)**(c)  
above, in a social network environment, data are updated with each event, such as adding or deleting friends, or interactions, such as comments or likes on posts. These data can be applied to human network analysis, user interest recommendations, etc. [11; 12; 13; 14; 15; 16]. In a dynamic environment, changes in the graph occur through the addition of new vertices, deletion of existing vertices, and creation and removal of edges. In such an environment, complex analysis and processing algorithms that reflect changes in the graph in real time are required. One of the main challenges in a dynamic environment is that the size of the graph continuously increases over time. To efficiently manage infinitely increasing data within limited storage space, graph compression is essential, allowing for the efficient use of storage space to accommodate increasing amounts of data [17; 18; 19; 20; 21; 22]. Techniques that incorporate graph pattern mining methods also exist [23; 24; 25; 26; 27; 28]. Generally, graph compression is performed using graph mining techniques to select frequently occurring sub-graphs as reference patterns, recording changes that occur in these reference patterns. These techniques can effectively compress data, while preserving important information from the graph. Existing methods of compressing graphs have the advantage of high compression rates [13; 22]; however, they are not suitable for real-time data processing owing to their significant computational costs in the preprocessing stage. These approaches involve a time-consuming compression process, especially imposing constraints on immediate processing in a graph stream environment. High accuracy and compression rates are provided by pattern extraction techniques, such as those in [14; 15; 16; 23; 24; 25; 26]; however, their long processing times during graph compression also render them difficult to be applied in real-time environments. As a solution to these issues, research on the use of provenance has been proposed [29; 30; 31]. Research studies often focus on summarizing graphs, but they frequently encounter limitations in compression rates. [PERSON], [PERSON] et al. introduced GSS, a sketch-based approach that delivers high update speed and accuracy for graph stream summarization [19]. However, the impact of GSS on compression rates under various graph stream characteristics requires further investigation. The existing methods based on the minimum description length or graph partitioning also demonstrate constraints in managing the dynamic nature of graph streams. To tackle these challenges, we propose a novel graph stream compression scheme that leverages provenance information to develop a pattern dictionary. The proposed scheme enables high compression rates while efficiently accommodating the evolving properties of graph streams. Provenance is metadata that track the change history and origin of data, allowing for the tracking of data changes. For example, in the case of Wikipedia, the process of multiple users creating, modifying, and deleting documents is recorded as provenance data, increasing the size of the original data by tens of times. This implies that managing provenance data can be more complex and challenging than managing the original data. However, if provenance data are used effectively, they can make graph storage more efficient and lead to more effective pattern management. In this paper, we propose a new graph stream compression scheme that combines existing techniques for compressing large static graphs with provenance techniques.