Abstract: User′s data stored on a cloud computing service provider may be tampered or deleted. The query integrity verification scheme enables a query user to verify that the data in the query results is authentic and all the data that meet the criteria are in the query results. As an improvement of the existing authenticated tree schemes， a space authenticated data structure， called verifiable SS-tree(VSS-tree)， is proposed to support spatial query and query authentication. The VSS-tree extends each node of SS-tree with authentication information. Boundary sphere is used for region shape which increases the degree of node and thus reduces the height of authenticated tree. Furthermore， it can avoid unnecessary disk access， which improves the processing efficiency of spatial query verification. Experimental results showed that VSS-tree can efficiently support spatial query and has better performance than MR-tree.

Key words: data outsourcing, k-nearest neighbor, spatial database, cloud computing, query authentication