ALBERT

Description:    Recently, several techniques have been proposed to protect the user location privacy for location-based services in the Euclidean space. Applying these techniques directly to the road network environment would lead to privacy leakage and inefficient query processing. In this paper, we propose a new location anonymization algorithm that is designed specifically for the road network environment. Our algorithm relies on the commonly used concept of spatial cloaking, where a user location is cloaked into a set of connected road segments of a minimum total length including at least users. Our algorithm is “query-aware” as it takes into account the query execution cost at a database server and the query quality, i.e., the number of objects returned to users by the database server, during the location anonymization process. In particular, we develop a new cost function that balances between the query execution cost and the query quality. Then, we introduce two versions of our algorithm, namely, pure greedy and randomized greedy , that aim to minimize the developed cost function and satisfy the user specified privacy requirements. To accommodate intervals with a high workload, we introduce a shared execution paradigm that boosts the scalability of our location anonymization algorithm and the database server to support large numbers of queries received in a short time period. Extensive experimental results show that our algorithms are more efficient and scalable than the state-of-the-art technique, in terms of both query execution cost and query quality. The results also show that our algorithms have very strong resilience to two privacy attacks, namely, the replay attack and the center-of-cloaked-area attack . Content Type Journal Article Pages 571-607 DOI 10.1007/s10707-010-0117-0 Authors Chi-Yin Chow, Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, China Mohamed F. Mokbel, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA Jie Bao, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA Xuan Liu, IBM Thomas J. Watson Research Center, Hawthorne, NY 10532, USA Journal GeoInformatica Online ISSN 1573-7624 Print ISSN 1384-6175 Journal Volume Volume 15 Journal Issue Volume 15, Number 3