Authenticated Subgraph Similarity Searchin Outsourced Graph Databases

Yun PENG, Zhe Fan, Koon Kau CHOI, Jianliang XU, Sourav S. Bhowmick

Research output: Contribution to journalJournal articlepeer-review

16 Citations (Scopus)


Subgraph similarity search is used in graph databases to retrieve graphs whose subgraphs are similar to a given query graph. It has been proven successful in a wide range of applications including bioinformatics and chem-informatics, etc. Due to the cost of providing efficient similarity search services on ever-increasing graph data, database outsourcing is apparently an appealing solution to database owners. Unfortunately, query service providers may be untrusted or compromised by attacks. To our knowledge, no studies have been carried out on the authentication of the search. In this paper, we propose authentication techniques that follow the popular filtering-and-verification framework. We propose an authentication-friendly metric index called GMTree. Specifically, we transform the similarity search into a search in a graph metric space and derive small verification objects (VOs) to-be-transmitted to query clients. To further optimize GMTree, we propose a sampling-based pivot selection method and an authenticated version of MCS computation. Our comprehensive experiments verified the effectiveness and efficiency of our proposed techniques.

Original languageEnglish
Article number6786998
Pages (from-to)1838-1860
Number of pages23
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
Publication statusPublished - 1 Jul 2015

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • outsourced database
  • query authentication
  • Subgraph similarity search


Dive into the research topics of 'Authenticated Subgraph Similarity Searchin Outsourced Graph Databases'. Together they form a unique fingerprint.

Cite this