Abstract: Location privacy receives considerable attentions in emerging location based services. Most current practices however either ignore users' preferences or incompletely fulfill privacy preferences. In this paper, we propose a privacy protection solution to allow users' preferences in the fundamental query of k nearest neighbors (kNN). Particularly, users are permitted to choose privacy preferences by specifying minimum inferred region. Via Hilbert curve based transformation, the additional workload from users' preferences is alleviated. Furthermore, this transformation reduces time-expensive region queries in 2-D space to range the ones in 1-D space. Therefore, the time efficiency, as well as communication efficiency, is greatly improved due to clustering properties of Hilbert curve. Further, details of choosing anchor points are theoretically elaborated. The empirical studies demonstrate that our implementation delivers both flexibility for users' preferences and scalability for time and communication costs.