Journal Title : International Journal of Modern Trends in Engineering and Science


Author’s Name : Pavithra K | Sreelakshmi Runnamed

Volume 04 Issue 04 2017

ISSN no :  2348-3121

Page no: 127-134

Abstract – Location-based services require users to continuously report their location to a potentially untrusted server to obtain services based on their location, which can expose them to privacy risks. Unfortunately, existing privacy-preserving techniques for Location-based services have several limitations, such as requiring a fully-trusted third party, offering limited privacy guarantees and incurring high communication overhead. In this paper, we propose a user-defined privacy grid system called dynamic grid system; the first holistic system that fulfills four essential requirements for privacy-preserving snapshot and continuous Location-based services. The system only requires a semi-trusted third party, responsible for carrying out simple matching operations correctly. This semi-trusted third party does not have any information about a user’s location. Secure snapshot and continuous location privacy is guaranteed under our defined adversary models. The communication cost for the user does not depend on the user’s desired privacy level, it only depends on the number of relevant points of interest in the vicinity of the user. Although we only focus on range and k-nearest-neighbor queries in this work, our system can be easily extended to support other spatial queries without changing the algorithms run by the semi-trusted third party and the database server, provided the required search area of a spatial query can be abstracted into spatial regions. Experimental results show that our dynamic grid system is more efficient than the state-of-the-art privacy-preserving technique for continuous Location-based services.

Key Words – location privacy; dynamic grid system; k-nearest neighbour; location-based service


  1. B. Gedik and L. Liu, “Protecting location privacy with personalized kanonymity:
  2. Architecture and algorithms,” IEEE TMC, vol. 7, no. 1, pp.1–18, 2008
  3. P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias, “Preventing location-based identity inference in anonymous spatial queries,” IEEE TKDE, vol. 19, no. 12, pp. 1719–1733, 2007.
  4. M. Kohlweiss, S. Faust, L. Fritsch, B. Gedrojc, and B. Preneel, “Efficient oblivious augmented maps: Location-based services with a payment broker,” in PET, 2007.
  5. R. Vishwanathan and Y. Huang, “A two-level protocol to answer private location-based queries,” in ISI, 2009.
  6. J.M. Kang,M. F.Mokbel, S. Shekhar, T. Xia, and D. Zhang, “Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors,” in IEEE ICDE, 2007.