Abstract
In this paper we propose a fundamental approach to perform the class of Nearest Neighbor (NN) queries, the core class of queries used in many of the location-based services, without revealing the origin of the query in order to preserve the privacy of this information. The idea behind our approach is to utilize one-way transformations to map the space of all static and dynamic objects to another space and resolve the query blindly in the transformed space. However, in order to become a viable approach, the transformation used should be able to resolve NN queries in the transformed space accurately and more importantly prevent malicious use of transformed data by untrusted entities. Traditional encryption based techniques incur expensive O(n) computation cost (where n is the total number of points in space) and possibly logarithmic communication cost for resolving a KNN query. This is because such approaches treat points as vectors in space and do not exploit their spatial properties. In contrast, we use Hilbert curves as efficient one-way transformations and design algorithms to evaluate a KNN query in the Hilbert transformed space. Consequently, we reduce the complexity of computing a KNN query to \(O(K\times\frac{2^{2N}}{n})\) and transferring the results to the client in O(K), respectively, where N, the Hilbert curve degree, is a small constant. Our results show that we very closely approximate the result set generated from performing KNN queries in the original space while enforcing our new location privacy metrics termed u-anonymity and a-anonymity, which are stronger and more generalized privacy measures than the commonly used K-anonymity and cloaked region size measures.
This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC), IIS-0238560 (PECASE), IIS-0324955 (ITR), and unrestricted cash gifts from Google and Microsoft. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Beresford, A.R., Stajano, F.: Location privacy in pervasive computing. IEEE Pervasive Computing 2(1), 46–55 (2003)
Bettini, C., Wang, X.S., Jajodia, S.: Protecting privacy against location-based personal identification. In: Jonker, W., Petković, M. (eds.) SDM 2005. LNCS, vol. 3674, pp. 185–199. Springer, Heidelberg (2005)
Faloutsos, C., Roseman, S.: Fractals for secondary key retrieval. In: PODS ’89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp. 247–252. ACM Press, New York, NY, USA (1989)
Gedik, B., Liu, L.: A customizable k-anonymity model for protecting location privacy
Gruteser, M., Grunwald, D.: Anonymous usage of location-based services through spatial and temporal cloaking. In: MobiSys. USENIX (2003)
Gruteser, M., Liu, X.: Protecting privacy in continuous location-tracking applications. IEEE Security & Privacy 2(2), 28–34 (2004)
Hilbert, D.: Uber die stetige abbildung einer linie auf ein flachenstuck. Math. Ann. 38, 459–460 (1891)
Indyk, P., Woodruff, D.P.: Polylogarithmic private approximations and efficient matching. In: Theory of Cryptography, Third Theory of Cryptography Conference, pp. 245–264. New York, NY, USA (2006)
Jagadish, H.V.: Linear clustering of objects with multiple atributes. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pp. 332–342. ACM Press, Atlantic City (1990)
Jagadish, H.V.: Analysis of the hilbert curve for representing two-dimensional space. Inf. Process. Lett. 62(1), 17–22 (1997)
Kalnis, P., Ghinita, G., Mouratidis, K., Papadias, D.: Preserving anonymity in location based services. A Technical Report TRB6/06, National University of Singapore (2006)
Lawder, J.K., King, P.J.H.: Querying multi-dimensional data indexed using the hilbert space-filling curve. SIGMOD Record 30(1), 19–24 (2001)
Mokbel, M.F.: Towards privacy-aware location-based database servers. In: Barga, R.S., Zhou, X. (eds.) ICDE Workshops, p. 93. IEEE Computer Society Press, Los Alamitos (2006)
Mokbel, M.F., Chow, C.-Y., Aref, W.G.: The new casper: Query processing for location services without compromising privacy. In: Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, pp. 763–774. ACM Press, New York (2006)
Moon, B., Jagadish, H.v., Faloutsos, C., Saltz, J.H.: Analysis of the clustering properties of the hilbert space-filling curve. IEEE Transactions on Knowledge and Data Engineering 13(1), 124–141 (2001)
Pinciroli, F., Combi, C., Pozzi, G., Negretto, M., Portoni, L., Invernizzi, G.: A peano hilbert derived algorithm for compression of angiocardiographic images. In: Computers in Cardiology, pp. 81–84. IEEE Computer Society Press, Los Alamitos (1991)
Sagan, H.: Space-Filling Curves. Springer, Heidelberg (1994)
Samarati, P., Sweeney, L.: Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression
Schroeder, M.R.: Number Theory in Science and Communication. Springer, Heidelberg (1984)
Stinson, D.R.: Cryptography, Theory and Practice. Chapman & Hall/CRC (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khoshgozaran, A., Shahabi, C. (2007). Blind Evaluation of Nearest Neighbor Queries Using Space Transformation to Preserve Location Privacy. In: Papadias, D., Zhang, D., Kollios, G. (eds) Advances in Spatial and Temporal Databases. SSTD 2007. Lecture Notes in Computer Science, vol 4605. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73540-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-73540-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73539-7
Online ISBN: 978-3-540-73540-3
eBook Packages: Computer ScienceComputer Science (R0)