G-hash: Towards Fast Kernel-based Similarity Search in Large Graph Databases

Structured data such as graphs and networks have posed significant challenges to fundamental aspects of data management including efficient storage, indexing, and similarity search. With the fast accumulation of graph databases, similarity search in graph databases has emerged as an important research topic. Graph similarity search has applications in a wide range of domains including chemoinformatics, bioinformatics, sensor network management, social network management, and XML documents, among others. Our objective in this thesis is to enable fast similarity search in large graph databases with graph kernel functions. In particular, we propose to develop (i) a novel kernel-based similarity measurement and (ii) an efficient indexing structure for graph data management. In our method we use a hash table to support efficient storage and fast search of the extracted local features from graph data. Using the hash table, we have developed a graph kernel function to capture the intrinsic similarity of graphs and for fast similarity query processing. We have demonstrated the utility of the proposed methods using large chemical structure graph databases.

Grantor dc:publisher

University of Kansas

Year dc:date.issued

2009

Author dc:creator

• Wang, Xiaohong

Advisors dc:contributor.advisor

• Huan, Jun
• Bai, Yong

• Computer Science
• Graph Kernel
• Graph similarity search
• Hashing

Statement dc:rights

• Copyright held by the author.

Language dc:language.iso

EN

Dc Identifier Other

http://dissertations.umi.com/ku:10622

OAI identifier oai:identifier

oai:kuscholarworks.ku.edu:1808/37069