k-anonymization is a widely used approach to protect the privacy of personal data. In many real-world applications, data is regularly accumulated, and the size of databases continues to grow over time. Anonymizing such dynamic databases poses significant computation time and efficiency challenges. This paper proposes an incremental framework to k-anonymization that processes only newly added records instead of re-anonymizing the whole data, thereby significantly reducing computational time for growing databases. Experiments were conducted on a real-world medical database containing 470,000 individuals’ records over 108-month period. Compared to existing methods, our framework achieved a 30 times speedup while keeping the loss information within 9%. This approach provides a scalable solution for privacy-preserving data utilization in continuously updated databases, offering practical benefits for real-world big data applications, such as in healthcare domains.