## 2 Related Work
For example, a pattern that appears early in the graph, but no longer appears later, may still be maintained in memory if it is large and has received a high score. This can lead to wasted storage space and performance degradation. This issue becomes more critical in a graph stream environment, wherein data change continuously. Therefore, considering changes in the importance of patterns over time is an essential element in graph stream compression. Our previous work introduced the idea of leveraging provenance metadata for the pattern-based compression of large RDF graphs [29; 30; 31]. The present study extends this approach to the more challenging context of graph streams, where the dynamic nature of data requires adaptive pattern mining and incremental compression. The studies reported suggest a graph pattern-based compression method for large RDF documents using metadata, namely provenance data, which represent information on or the history of the data. This method uses an approach that reduces the size of string data by encoding specific graph patterns. While this study exhibits superior compression performance to existing methods, it uses a statistics-based compression approach, which means that the compression performance can vary with parameter adjustments, and some data loss can possibly occur. Furthermore, the compression process using provenance data can take longer than the existing techniques do. This is because compression methods including provenance data require processing and storing additional information. This is a significant factor impacting their overall performance as finding a balance between compression efficiency and processing time can be a major constraint, especially in applications where real-time data processing is emphasized. In graph stream environments, the size and arrival speed of data make it difficult to process them efficiently with traditional graph storage structures. Therefore, graph summarization or graph compression techniques are essential to effectively handling graph streams. Graph summarization aims to reduce the size of a graph while maintaining its characteristics and structure, while graph compression is reversible, allowing the original graph to be restored from its compressed form. [PERSON] et al. proposed a graph stream compression technique called Graph Stream Sketch (GSS) [19]. GSS has linear memory usage and a high update speed, and supports most graph queries. It also shows much higher accuracy compared with that of existing methods. GSS compresses the original graph into a small graph sketch using hash functions and stores it in a novel data structure that combines fingerprints and hash addresses for differentiation. However, GSS has the limitation of high time costs when performing successor/precursor queries, as it needs to scan the mapped rows or columns. Moreover, the compression efficiency of GSS is not very high, resulting in lower compression ratios compared with existing lossless compression methods. Existing graph compression techniques, primarily designed for static graphs, struggle to address the unique challenges posed by graph streams, such as high update rates, temporal dynamics, and scalability. To overcome these limitations, we propose a novel graph stream compression scheme that leverages provenance information to capture the temporal evolution of patterns. The proposed scheme maintains a dynamic dictionary of patterns and exploits their relationships to achieve high compression rates while supporting efficient update and query processing, thereby addressing the challenges of graph stream compression.