Authenticated Subgraph Similarity Searchin Outsourced Graph Databases

摘要

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 of the search. In this paper, we propose authentication techniques that follow the popular framework. We propose an authentication-friendly metric index called . Specifically, we transform the similarity search into a search in a graph metric space and derive small verification objects (s) to-be-transmitted to query clients. To further optimize , we propose a sampling-based pivot selection method and an authenticated version of computation. Our comprehensive experiments verified the effectiveness and efficiency of our proposed techniques.