Closure-Tree: An Index Structure for Graph Queries

Brief Description

A graph comparison technique that can support both subgraph and similarity queries.

Background

Recent technological and scientific advances have resulted in an abundance of data that describe and model phenomena as primitive components and relationships between them. Overtime, graphs have gained increasing popularity for modeling structured data. As a result, graph queries are becoming common and graph indexing has come to play an essential role in query processing.

Description

Researchers at the University of California, Santa Barbara, have developed a new graph comparison technique, known as Closure-tree or C-tree. C-tree is the first index structure that can support both subgraph and similarity queries. Subgraph queries involve looking for a specific pattern in a graph. They are useful for a number of applications including identification of similar protein structures, finding similar biological pathways such as protein interaction networks, identification of similar chemical compounds, and identification of targets and leads during drug discovery. Experiments on chemical compounds and synthetic graphs show that, for subgraph queries, C-tree outperforms existing techniques by up to two orders of magnitude. Similarity queries involve looking for a graph that is similar to another graph. Similarity queries can be used for applications such as schema matching and classification.

Advantages

Applications

Patent Status