TY - GEN
T1 - Bichromatic reverse nearest neighbor query without information leakage
AU - Wang, Lu
AU - Meng, Xiaofeng
AU - Hu, Haibo
AU - Xu, Jianliang
N1 - Publisher Copyright:
© 2015, Springer International Publishing Switzerland, All rights Reserved.
PY - 2015
Y1 - 2015
N2 - Bichromatic Reverse Nearest Neighbor (BRNN) Query is an important query type in location-based services (LBS) and has many real life applications, such as site selection and resource allocation. However, such query requires the client to disclose sensitive location information to the LBS. The only existing method for privacy-preserving BRNN 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 retrieval (PIR) technique, which accesses data pages anonymously from a database. Based on PIR, we propose a secure query processing framework together with various indexing and optimization techniques. To the best knowledge, this is the first research that preserves strong location privacy in BRNN query. Extensive experiments under real world and synthetic datasets demonstrate the practicality of our approach.
AB - Bichromatic Reverse Nearest Neighbor (BRNN) Query is an important query type in location-based services (LBS) and has many real life applications, such as site selection and resource allocation. However, such query requires the client to disclose sensitive location information to the LBS. The only existing method for privacy-preserving BRNN 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 retrieval (PIR) technique, which accesses data pages anonymously from a database. Based on PIR, we propose a secure query processing framework together with various indexing and optimization techniques. To the best knowledge, this is the first research that preserves strong location privacy in BRNN query. Extensive experiments under real world and synthetic datasets demonstrate the practicality of our approach.
KW - Bichromatic RNN
KW - Location privacy
KW - Privacy preservation
KW - Private information retrieval
UR - http://www.scopus.com/inward/record.url?scp=84942564980&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-18120-2_35
DO - 10.1007/978-3-319-18120-2_35
M3 - Conference proceeding
AN - SCOPUS:84942564980
SN - 9783319181196
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 609
EP - 624
BT - Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Proceedings Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part I
A2 - Shahabi, Cyrus
A2 - Cheema, Muhammad Aamir
A2 - Renz, Matthias
A2 - Zhou, Xiaofang
PB - Springer Verlag
T2 - 20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Y2 - 20 April 2015 through 23 April 2015
ER -