Authentication of Top- Spatial Keyword Queries in Outsourced Databases

In this paper, we study the authentication of top-

$$k$$

spatial keyword queries in outsourced databases. We first present a scheme based on tree-forest indexes, which consist of an MR-tree (which is the state-of-the-art authenticated data structure for the authentication of spatial queries) and a collection of Merkle term trees (MT-trees). The tree-forest indexes can support efficient top-

$$k$$

spatial keyword query (

$$k$$

SKQ) processing and authentication. To derive a small verification object (VO) to be returned to the user, we put forward an entry pruning based scheme, where an MT*-tree is presented. The entries in each node of MT*-tree are ordered and an embedded Merkle hash tree (embedded-MHT) is constructed over them. By employing a novel pruning strategy, the redundant entries in each node of MT*-trees can be eliminated from VO. Our extensive experiments verify the effectiveness, efficiency and scalability of our proposed schemes on several performance metrics, including the index construction time, index size, running time, VO size and authentication time.