Closure-Tree: An Index Structure for Graph Queries

Tech ID: 29298 / UC Case 2006-251-0

Brief Description

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


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.


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.


  • Supports both subgraph queries and similarity queries
  • Extends many techniques developed for spatial access methods
  • Graph closures capture the entire structural information of constituent graphs, which implies high pruning rates
  • Dynamic insertion/deletion and disk-based access of graphs can be done efficiently
  • Avoids an exhaustive enumeration procedure as in GraphGrep and GIndex


  • Drug discovery
  • Schema matching
  • Classification

Patent Status

Country Type Number Dated Case
United States Of America Issued Patent 8,396,884 03/12/2013 2006-251


Learn About UC TechAlerts - Save Searches and receive new technology matches


  • Camoglu, Orhan
  • Can, Tolga
  • He, Huahai
  • Ranu, Sayan
  • Singh, Ambuj K.

Other Information


indansens; indsoftw

Categorized As