TY - GEN
T1 - Authentication of top-k spatial keyword queries in outsourced databases
AU - Su, Sen
AU - Yan, Han
AU - Cheng, Xiang
AU - Tang, Peng
AU - Xu, Peng
AU - Xu, Jianliang
N1 - Publisher Copyright:
© 2015, Springer International Publishing Switzerland, All rights Reserved.
PY - 2015
Y1 - 2015
N2 - 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 stateof- 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 (kSKQ) 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.
AB - 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 stateof- 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 (kSKQ) 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.
UR - http://www.scopus.com/inward/record.url?scp=84942611523&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-18120-2_33
DO - 10.1007/978-3-319-18120-2_33
M3 - Conference proceeding
AN - SCOPUS:84942611523
SN - 9783319181196
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 567
EP - 588
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 -