Query-aware location anonymization for road networks

被引:38
作者
Chow, Chi-Yin [2 ]
Mokbel, Mohamed F. [1 ]
Bao, Jie [1 ]
Liu, Xuan [3 ]
机构
[1] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA
[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
[3] IBM Thomas J Watson Res Ctr, Hawthorne, NY 10532 USA
基金
美国国家科学基金会;
关键词
Location privacy; Shared execution; Location-based services; Spatial network databases; GIS; K-ANONYMITY;
D O I
10.1007/s10707-010-0117-0
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 L including at least K 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.
引用
收藏
页码:571 / 607
页数:37
相关论文
共 35 条
[1]  
BAMBA B, 2008, P INT WORLD WID WEB
[2]  
CHENG R, 2006, P INT PRIV ENH TECHN
[3]   Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments [J].
Chow, Chi-Yin ;
Mokbel, Mohamed F. ;
Liu, Xuan .
GEOINFORMATICA, 2011, 15 (02) :351-380
[4]   A Privacy-Preserving Location Monitoring System for Wireless Sensor Networks [J].
Chow, Chi-Yin ;
Mokbel, Mohamed F. ;
He, Tian .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2011, 10 (01) :94-107
[5]   Casper: Query Processing for Location Services without Compromising Privacy [J].
Chow, Chi-Yin ;
Mokbel, Mohamed F. ;
Aref, Walid G. .
ACM TRANSACTIONS ON DATABASE SYSTEMS, 2009, 34 (04)
[6]  
CHOW CY, 2006, P ACM S ADV GEOGR IN
[7]  
CHOW CY, 2007, P INT S SPAT TEMP DA
[8]  
DUCKHAM M, 2005, P INT C PERV COMP
[9]   Protecting location privacy with personalized k-anonymity:: Architecture and algorithms [J].
Gedik, Bugra ;
Liu, Ling .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2008, 7 (01) :1-18
[10]  
GHINITA G, 2007, P INT WORLD WID WEB