Authenticated Subgraph Similarity Searchin Outsourced Graph Databases

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

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

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
Volume27
Issue number7
DOIs
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

Fingerprint

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

Cite this