Authentication of top-k spatial keyword queries in outsourced databases

Sen Su*, Han Yan, Xiang Cheng, Peng Tang, Peng Xu, Jianliang Xu

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

13 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Proceedings Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part I
EditorsCyrus Shahabi, Muhammad Aamir Cheema, Matthias Renz, Xiaofang Zhou
PublisherSpringer Verlag
Pages567-588
Number of pages22
ISBN (Print)9783319181196
DOIs
Publication statusPublished - 2015
Event20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam
Duration: 20 Apr 201523 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9049
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Country/TerritoryViet Nam
CityHanoi
Period20/04/1523/04/15

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Authentication of top-k spatial keyword queries in outsourced databases'. Together they form a unique fingerprint.

Cite this