Since querying with traditional cloaking region has brought too much communication cost due to the returned useless points of interest (PoI),a new cloaking region constructing method was proposed.Firstly,LBS server divided the whole map into cells according to PoIs’ locations with Voronoi partition,then the Voronoi partition was organized with quadtree into a hierarchical structure,the leaf nodes of the quadtree represented minimum grid cells,and each grid cell contained several PoIs;Finally,LBS server sent the subtree to a user according to the user’s fake location,the user got the PoIs distribution around him and constructed the cloaking region according to the distribution.The method protected the user’s location and query privacy,and the hormic PoI query decreased the communication cost of the useless PoIs.Performance analysis and experiments showed that this method increases the uncertainty of users’ private information to attackers,and its communication cost is lower.
