The　existing　k-anonymity　model　protects　against　identity　disclosure,　but　it　fails　to　protect　against　attribute　disclosure.　To　avoid　this　shortcoming,　some　privacy　preserving　data　release　models　were　presented.　However,　most　of　these　privacy　preserving　models　focuses　on　generalization　and　suppression　technique,　which　lead　to　superabundant　information　loss.　Moreover,　some　researcher　have　proven　it　is　a　NP-hardness　problem.　To　minimize　the　information　loss　incurred　in　the　anonymity　process,　we　propose　a　enforce　privacy-preserving　paradigm　of　p-sensitive　k-anonymity　and　use　a　nearest　neighbor　search　algorithm　to　achieve　it.　We　group　similar　data　together　first,　and　then　publish　each　group　individually　for　this　paradigm.　Our　preliminary　experimental　results　indicate　that　our　algorithm　not　only　provides　a　stronger　privacy　protection　but　also　results　in　better　utility　of　anonymous　data.　©　2012　by　Binary　Information　Press.