GADDI: distance index based subgraph matching in biological networks. Currently, a huge amount of biological data can be naturally represented by graphs, e.g., protein interaction networks, gene regulatory networks, etc. The need for indexing large graphs is an urgent research problem of great practical importance. The main challenge is size. Each graph may contain thousands (or more) vertices. Most of the previous work focuses on indexing a set of small or medium sized database graphs (with only tens of vertices) and finding whether a query graph occurs in any of these. In this paper, we are interested in finding all the matches of a query graph in a given large graph of thousands of vertices, which is a very important task in many biological applications. This increases the complexity significantly. We propose a novel distance measurement which reintroduces the idea of frequent substructures in a single large graph. We devise the novel structure distance based approach (GADDI) to efficiently find matches of the query graph. GADDI is further optimized by the use of a dynamic matching scheme to minimize redundant calculations. Last but not least, a number of real and synthetic data sets are used to evaluate the efficiency and scalability of our proposed method.

References in zbMATH (referenced in 5 articles )

Showing results 1 to 5 of 5.
Sorted by year (citations)

  1. Pal, Dipali; Rao, Praveen; Slavov, Vasil; Katib, Anas: Fast processing of graph queries on a large database of small and medium-sized data graphs (2016)
  2. Lee, Chun-Hee; Chung, Chin-Wan: Efficient search in graph databases using cross filtering (2014)
  3. Zheng, Weiguo; Zou, Lei; Lian, Xiang; Zhang, Huaming; Wang, Wei; Zhao, Dongyan: SQBC: an efficient subgraph matching method over large and dense graphs (2014)
  4. Zhu, Linhong; Ng, Wee Keong; Cheng, James: Structure and attribute index for approximate graph matching in large graphs (2011) ioport
  5. Lipets, V.; Vanetik, N.; Gudes, E.: Subsea: an efficient heuristic algorithm for subgraph isomorphism (2009) ioport