Abstract:

Currently, the each iteration of most location anonymous clustering algorithms is required to traverse all users’ locations to find the nearest user from the centroid of the anonymous box, which consumes a lot of time and does not provide better protection to query privacies that contain more sensitive information. To solve these problems, this paper proposes a query privacy anonymity algorithm based on grid clustering (QPAGC). The algorithm regards grid as the processing unit and all users’ positions can be located to a grid, which does not traverse the specific location of each user. The algorithm calculates the centroid of anonymous box and centroids of all the neighborhood grids, the neighborhood grid which its centroid is nearest from the centroid of anonymous box is added to anonymous box until the quality of anonymous box satisfies the requirement of k-anonymity constraint. Anonymous box satisfies p-sensitive constraint by adding fake users and fake requests to protect user’s query privacy. Contrast experiment shows that query privacy anonymity algorithm based on grid clustering has a higher success rate of anonymity and a smaller anonymous area, increases relative anonymity and the quality of the user’s query service by meeting the requirements of individual user, so the method balances the contradiction between the safety factor of k and QoS.

Key words: location-based service, grid clustering, k-anonymity, centroid, query privacy