Nowadays, there are many organizations publishing and sharing their databases with other parties for different purposes, such as to conduct statistical surveys, business investigations, or health studies. However, this shared information is mostly public, and adversaries can use it to reveal and expose real identities; therefore, it is important for database owners to preserve the privacy of the individual's data. Previous researches in data anonymity have provided different privacy-preserving methods for protecting published data. However, the utility of the anonymized databases remains an important challenge and requires further studies. In this paper, we proposed a new way to increase the utility of the anonymized databases. We integrated kNN, a classification method, with k-anonymity to measure the similarities among multiple records. Finally, we show an example of how kNN can significantly maximizing the utility of the released databases while preserving data privacy.