Query Authentication of Outsourced
Spatial Database
Jun Hong1,2, Tao Wen2, and Quan
Guo3
1School of Software, North
University of China, China
2School of Computer Science and
Engineering, Northeastern University, China
3Computer
Science and Technology, Dalian Neusoft University of Information, China
Abstract: Outsourcing spatial database to a third party is
becoming a common practice for more and more individuals and companies to save
the cost of managing and maintaining database, where a data owner delegates its
spatial data management tasks to a third party and grants it to provide query
services. However, the third party is not full trusted. Thus, authentication
information should be provided to the client for query authentication. In this
paper, we introduce an efficient space authenticated data structure, called Verifiable Similarity Indexing
tree (VSS-tree), to support authenticated spatial query. We build VSS-tree
based on SS-tree which employs bounding sphere rather than bounding rectangle
for region shape and extend it with authentication information. Based on
VSS-tree, the third party finds query results and builds their corresponding
verification object. The client performs query authentication using the
verification object and the public key published. Finally, we evaluate the
performance and validity of our algorithms, the experiment results show that
VSS-tree can efficiently support spatial query and have better performance than
Merkle R tree (MR-tree).
Keywords: Data Outsourcing, KNN, spatial database, cloud computing,
query authentication.
Received February 7, 2017; accepted December 24,
2018