TY - GEN
T1 - Distributed kNN query authentication
AU - Xu, Cheng
AU - XU, Jianliang
AU - CHOI, Koon Kau
N1 - Funding Information:
ACKNOWLEDGEMENTS This work was supported by Research Grants Council of Hong Kong under GRF Projects 12244916, 12202414, 12232716, and CRF Project C1008-16G.
PY - 2018/7/13
Y1 - 2018/7/13
N2 - With the prevalence of location-based services and geo-functioned devices, the trend of spatial data outsourcing is rising. In the data outsourcing scenario, result integrity must be ensured by means of a query authentication scheme. However, most of the existing studies are confined to a centralized environment. In this paper, we investigate the query authentication problem in distributed environments and focus on the k nearest neighbor (kNN) query, which is widely used in spatial data analytics. We design a new distributed spatial authenticated data structure (ADS), distributed MR-tree, to facilitate efficient kNN processing. Furthermore, we propose a basic algorithm to process authenticated kNN queries based on the new ADS. Apart from the results, some verification objects are generated to guarantee the results' integrity. We also design two optimized algorithms to reduce the size of verification objects as well as the verification cost. Our experiments validate the good performance of the proposed techniques in terms of query cost, communication overhead, and verification time.
AB - With the prevalence of location-based services and geo-functioned devices, the trend of spatial data outsourcing is rising. In the data outsourcing scenario, result integrity must be ensured by means of a query authentication scheme. However, most of the existing studies are confined to a centralized environment. In this paper, we investigate the query authentication problem in distributed environments and focus on the k nearest neighbor (kNN) query, which is widely used in spatial data analytics. We design a new distributed spatial authenticated data structure (ADS), distributed MR-tree, to facilitate efficient kNN processing. Furthermore, we propose a basic algorithm to process authenticated kNN queries based on the new ADS. Apart from the results, some verification objects are generated to guarantee the results' integrity. We also design two optimized algorithms to reduce the size of verification objects as well as the verification cost. Our experiments validate the good performance of the proposed techniques in terms of query cost, communication overhead, and verification time.
KW - Distributed Systems
KW - kNN
KW - Query Authentication
UR - http://www.scopus.com/inward/record.url?scp=85050810549&partnerID=8YFLogxK
U2 - 10.1109/MDM.2018.00034
DO - 10.1109/MDM.2018.00034
M3 - Conference contribution
AN - SCOPUS:85050810549
T3 - Proceedings - IEEE International Conference on Mobile Data Management
SP - 167
EP - 176
BT - Proceedings - 2018 IEEE 19th International Conference on Mobile Data Management, MDM 2018
PB - IEEE
T2 - 19th IEEE International Conference on Mobile Data Management, MDM 2018
Y2 - 26 June 2018 through 28 June 2018
ER -