A privacy-protected k-NN query processing algorithm based on weighted adjacency graph for locationbased services

Due to the advances of mobile devices with GPS (Global Positioning System), a user' privacy threat is increased in location based services (LBSs). So, in LBSs, it is important to process given queries efficiently while protecting users' privacy with a low bandwidth usage. For this, a 2PASS was proposed to search k-nearest POIs by generating cloaking regions which can hide the actual user location and reduce the bandwidth consumption. However, this method suffers from privacy attack. Therefore, we, in this paper, propose a privacy-protected k-NN query processing algorithm based on Weighted Adjacency Graph for Location-based services. Our privacy-protected k-NN query processing algorithm can reduce bandwidth usages and efficiently support k-nearest neighbor queries without revealing the private information of the query issuer. With performance evaluation, we show that our scheme outperforms the existing one.