Enabling Efficient Update on Rule-Based Compressed Graph
Lin Feng, Feng Zhang, Zheng Chen, Yuxin Tang, Jiawei Guan, Xiaowei Zhu, Xiaoyong Du · Proceedings of the ACM on Management of Data · 2026
Dynamic graphs, pivotal in applications ranging from social networks to biological systems, pose significant challenges in storage and update efficiency due to their continuous evolution through insertions and deletions. Traditional graph compression methods, primarily optimized for static graphs, often struggle in dynamic environments, leading to costly decompression-recompression cycles during updates. To address this limitation, we propose a novel theoretical framework that enables efficient direct updates on rule-based compressed graphs. Additionally, we introduce a dynamic graph processing framework that balances space efficiency, update responsiveness, and query performance. Our framework treats updates as lightweight, localized modifications, sustains compression via background cleanup, and preserves query performance by ensuring structural integrity. Our method achieves significant memory savings, reducing usage by an average of 50.1% over state-of-the-art dynamic compressed graph systems, while demonstrating highly competitive update throughput and query performance. These advancements establish a scalable, high-performance solution for dynamic graph management, effectively bridging the gap between space efficiency, updates responsiveness and query performance.