Graph indexing for large networks: A neighborhood tree-based approach
Graph indexing for large networks: A neighborhood tree-based approach
复制标题
DOI：
10.1016/j.knosys.2014.08.025
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Zhen Lin;Yijun Bei
中科院分区：
文献类型：
--
作者：
Zhen Lin;Yijun Bei
Graphs are used to model complex data objects and their relationships in the real world. Finding occurrences of graph patterns in large graphs is one of the fundamental graph analysis tools used to discover underlying characteristics from these complex networks. In this paper, we propose a new tree-based approach for improving subgraph-matching performance. First, we introduce a new graph indexing mechanism known asNeighborhoodTrees (NTree), which records the neighborhood relationships of each vertex in the large graph to filter negative vertices. Second, we decompose a query graph into a set of neighborhood trees and only a subset of candidate trees, which can properly recover the original query graph. In this way, the tree-at-a-time method is used to obtain the matched graphs. Third, we employ a graph query optimizer to determine the neighborhood tree selection order on the basis of the cost evaluation of tree join operations. Experiments on both real and synthetic databases demonstrate that our approach is more efficient than other state-of-the-art indexing methods.
