Abstract
In location based services, users can request interesting services around them at any time and anywhere through mobile devices. They need to send their locations to get the service, which may cause the disclosure of their location privacy. In order to protect the location privacy, a typical way is to convert the specific location into a location area. After finding the interest points around the region, the server needs to refine the result set to get the exact result of the query. In this article, we extended the existing kNN query algorithm based on the circular region, and proposed an algorithm called EkCRNN. This algorithm used an anonymous server to exchange information between the user and the LBS server. We compared two algorithms through experiments, and the experimental results show that our algorithm has higher accuracy.