Authenticated Sub graph Similarity Search in Outsourced Graph Databases
Abstract:
Subgraph similarity search is used in graph databases to retrieve graphs whose subgraphs are similar to a given querygraph. It has been proven successful in a wide range of applications including bioinformatics and chem-informatics, etc. Due to the costof providing efficient similarity search services on ever-increasing graph data, database outsourcing is apparently an appealing solutionto database owners. Unfortunately, query service providers may be untrusted or compromised by attacks. To our knowledge, nostudies 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, wetransform the similarity search into a search in a graph metric space and derive small verification objects (VOs) to-be-transmitted toquery clients. To further optimize GMTree, we propose a sampling-based pivot selection method and an authenticated version of MCScomputation. Our comprehensive experiments verified the effectiveness and efficiency of our proposed techniques
Existing system:
Similarity search is known to be an NP-hard problem.The owners of graph databases may lack the IT resourcesand expertises to provide efficient searches of their databases.For example, we issued a small query for a benzenestructure to the prototype of a recent chemical database and the query took 7.8 minutes. Such a performancemay not be ideal for many applications.Further, graph data is growing explosively in volume.
Proposed system:
In this paper, we propose authentication techniques that follow thepopular filtering-and-verification framework. We propose an authentication-friendly metric index called GMTree. Specifically, wetransform the similarity search into a search in a graph metric space and derive small verification objects (VOs) to-be-transmitted toquery clients. To further optimize GMTree, we propose a sampling-based pivot selection method and an authenticated version of MCScomputation. Our comprehensive experiments verified the effectiveness and efficiency of our proposed techniques
System architecture:
SYSTEM REQUIREMENTS:
HARDWARE REQUIREMENTS:
System: Pentium IV 2.4 GHz.
Hard Disk : 40 GB.
Floppy Drive: 1.44 Mb.
Monitor: 15 VGA Colour.
Mouse: Logitech.
Ram: 512 Mb.
SOFTWARE REQUIREMENTS:
Operating system : Windows XP/7.
Coding Language: JAVA/J2EE
IDE:Netbeans 7.4
Database:MYSQL
Further Details Contact: A Vinay 9030333433, 08772261612
Email: |