Skip to main content

2015 | OriginalPaper | Buchkapitel

Evaluating k Nearest Neighbor Query on Road Networks with no Information Leakage

verfasst von : Lu Wang, Ruxia Ma, Xiaofeng Meng

Erschienen in: Web Information Systems Engineering – WISE 2015

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The development of positioning technologies and pervasiveness of mobile devices make an upsurge of interest in location based services (LBS). The k nearest neighbor(kNN) query in road networks is an important query type in LBS and has many real life applications, such as map service. However, such query requires the client to disclose sensitive location information to the LBS. The only existing method for privacy-preserving kNN query adopts the cloaking-region paradigm, which blurs the location into a spatial region. However, the LBS can still deduce some information (albeit not exact) about the location. In this paper, we aim at strong privacy wherein the LBS learns nothing about the query location. To this end, we employ private information retrivial (PIR) technique, which accesses data pages anonymously from a database. Based on PIR, we propose a secure query processing framework together with flexible query plan for arbitrary kNN query. To the best of our knowledge, this is the first research that preserves strong location privacy for network kNN query. Extensive experiments under real world and synthetic datasets demonstrate the practicality of our approach.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Mokbel, M.F., Chow, C.Y., Aref, W.G.: The new casper: query processing for location services without compromising privacy. In: VLDB, pp. 763–774 (2006) Mokbel, M.F., Chow, C.Y., Aref, W.G.: The new casper: query processing for location services without compromising privacy. In: VLDB, pp. 763–774 (2006)
2.
Zurück zum Zitat Yiu, M.L., Jensen, C., Huang, X., Lu, H.: Spacetwist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile systems. In: ICDE, pp. 366–375 (2008) Yiu, M.L., Jensen, C., Huang, X., Lu, H.: Spacetwist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile systems. In: ICDE, pp. 366–375 (2008)
3.
Zurück zum Zitat Wong, W.K., Cheung, D.Q., Kao, B., Manoulis, N.: Secure kNN Computation on encrypted databases. In: SIGMOD, pp. 139–152 (2009) Wong, W.K., Cheung, D.Q., Kao, B., Manoulis, N.: Secure kNN Computation on encrypted databases. In: SIGMOD, pp. 139–152 (2009)
4.
Zurück zum Zitat Khoshgozaran, A., Shahabi, C., Shirani-Mehr, H.: Location privacy: going beyond k-anonymity, cloaking and anonymizers. KAIS 26(1), 435–465 (2011) Khoshgozaran, A., Shahabi, C., Shirani-Mehr, H.: Location privacy: going beyond k-anonymity, cloaking and anonymizers. KAIS 26(1), 435–465 (2011)
5.
Zurück zum Zitat Jung-Ho, U., Yong-Ki, K., Hyun-Jo, L., Miyoung, J., Jae-Woo, C.: K nearest neighbor query processing algorithm for cloaking regions towards user privacy protection in location-based services. J. Syst. Archit. EUROMICRO J. 58(9), 354–371 (2012)CrossRef Jung-Ho, U., Yong-Ki, K., Hyun-Jo, L., Miyoung, J., Jae-Woo, C.: K nearest neighbor query processing algorithm for cloaking regions towards user privacy protection in location-based services. J. Syst. Archit. EUROMICRO J. 58(9), 354–371 (2012)CrossRef
6.
Zurück zum Zitat Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: FOCS, pp. 364–373 (1997) Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: FOCS, pp. 364–373 (1997)
7.
Zurück zum Zitat Papadopoulos, S., Bakiras, S., Papadias, D.: Nearest neighbor search with strong location privacy. Proc. VLDB 3, 619–629 (2010)CrossRef Papadopoulos, S., Bakiras, S., Papadias, D.: Nearest neighbor search with strong location privacy. Proc. VLDB 3, 619–629 (2010)CrossRef
8.
Zurück zum Zitat Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., Tan, K.-L.: Private queries in location based services: anonymizers are not necessary. In: SIGMOD (2008) Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., Tan, K.-L.: Private queries in location based services: anonymizers are not necessary. In: SIGMOD (2008)
9.
Zurück zum Zitat Mouratidis, K., Yiu, M.L.: Shortest path computation with no information leakage. PVLDB 5(1), 692–703 (2012) Mouratidis, K., Yiu, M.L.: Shortest path computation with no information leakage. PVLDB 5(1), 692–703 (2012)
10.
Zurück zum Zitat Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.-F.: Breaking the O(n1/(2k–1)) barrier for information-theoretic private information retrieval. In: Proceedings of FOCS, pp. 261–270 (2002) Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.-F.: Breaking the O(n1/(2k–1)) barrier for information-theoretic private information retrieval. In: Proceedings of FOCS, pp. 261–270 (2002)
12.
Zurück zum Zitat Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005) CrossRef Gentry, C., Ramzan, Z.: Single-database private information retrieval with constant communication rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005) CrossRef
13.
Zurück zum Zitat Wang, L., Meng, X., Hu, H., Xu, J.: Bichromatic reverse nearest neighbor query without information leakage. In: Renz, M., Shahabi, C., Zhou, X., Cheema, M.A. (eds.) DASFAA 2015. LNCS, vol. 9049, pp. 609–624. Springer, Heidelberg (2015) Wang, L., Meng, X., Hu, H., Xu, J.: Bichromatic reverse nearest neighbor query without information leakage. In: Renz, M., Shahabi, C., Zhou, X., Cheema, M.A. (eds.) DASFAA 2015. LNCS, vol. 9049, pp. 609–624. Springer, Heidelberg (2015)
14.
Zurück zum Zitat Williams, P., Sion, R.: Usable PIR. In: NDSS (2008) Williams, P., Sion, R.: Usable PIR. In: NDSS (2008)
15.
Zurück zum Zitat Naor, M., Pinkas, B.: Oblivious transfer with adaptive queries. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 573–590. Springer, Heidelberg (1999) CrossRef Naor, M., Pinkas, B.: Oblivious transfer with adaptive queries. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 573–590. Springer, Heidelberg (1999) CrossRef
16.
Zurück zum Zitat Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999) CrossRef Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999) CrossRef
17.
Zurück zum Zitat Paulet, R., Kaosar, Md.G., Yi, X., Bertino, E.: Privacy-preserving and content-protecting location based queries. In: ICDE, pp. 44–53 (2012) Paulet, R., Kaosar, Md.G., Yi, X., Bertino, E.: Privacy-preserving and content-protecting location based queries. In: ICDE, pp. 44–53 (2012)
18.
Zurück zum Zitat Yi, X., Paulet, R., Bertino, E., Varadharajan, V.: Practical k nearest neighbor queries with location privacy. In: ICDE, pp. 640–651 (2014) Yi, X., Paulet, R., Bertino, E., Varadharajan, V.: Practical k nearest neighbor queries with location privacy. In: ICDE, pp. 640–651 (2014)
20.
Zurück zum Zitat Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: SODA, pp. 156–165 (2005) Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: SODA, pp. 156–165 (2005)
21.
Zurück zum Zitat Lee, K.C.K., Lee, W.-C., Zheng, B.: Fast object search on road networks. In: EDBT, pp. 1018–1029 (2009) Lee, K.C.K., Lee, W.-C., Zheng, B.: Fast object search on road networks. In: EDBT, pp. 1018–1029 (2009)
22.
Zurück zum Zitat Kolahdouzan, M., Shahabi, C.: Voronoi-based K nearest neighbor search for spatial network databases. In: VLDB, pp. 840–851 (2004) Kolahdouzan, M., Shahabi, C.: Voronoi-based K nearest neighbor search for spatial network databases. In: VLDB, pp. 840–851 (2004)
23.
Zurück zum Zitat Hu, H., Lee, D.-L., Xu, J.: Fast nearest neighbor search on road networks. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., Böhm, K., Kemper, A., Grust, T., Böhm, C. (eds.) EDBT 2006. LNCS, vol. 3896, pp. 186–203. Springer, Heidelberg (2006) CrossRef Hu, H., Lee, D.-L., Xu, J.: Fast nearest neighbor search on road networks. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., Böhm, K., Kemper, A., Grust, T., Böhm, C. (eds.) EDBT 2006. LNCS, vol. 3896, pp. 186–203. Springer, Heidelberg (2006) CrossRef
24.
Zurück zum Zitat Safar, M.: K nearest neighbor search in navigation systems. Mob. Inf. Syst. 1(3), 207–224 (2005) Safar, M.: K nearest neighbor search in navigation systems. Mob. Inf. Syst. 1(3), 207–224 (2005)
25.
Zurück zum Zitat Narayanan, A., Shmatikov, V.: Robust De-anonymization of large sparse datasets. In: IEEE Symposium on Security and Privacy, pp 111–125 (2008) Narayanan, A., Shmatikov, V.: Robust De-anonymization of large sparse datasets. In: IEEE Symposium on Security and Privacy, pp 111–125 (2008)
26.
Zurück zum Zitat Jensen, C., Kolarvr, J., Pedersen, T.B., Timko, I.: Nearest neighbor queries in road networks. In: GIS, pp. 1–8 (2003) Jensen, C., Kolarvr, J., Pedersen, T.B., Timko, I.: Nearest neighbor queries in road networks. In: GIS, pp. 1–8 (2003)
Metadaten
Titel
Evaluating k Nearest Neighbor Query on Road Networks with no Information Leakage
verfasst von
Lu Wang
Ruxia Ma
Xiaofeng Meng
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-26190-4_34