A subgraph query algorithm based on two-step mapping on vertex to decision feature

被引：0

作者：

Li X. ^{[1
]}

Li J. ^{[1
]}

机构：

[1] School of Computer Science and Technology, Harbin Institute of Technology

来源：

Gaojishu Tongxin/Chinese High Technology Letters | 2010年 / 20卷 / 03期

关键词：

Decision feature; Frequent feature; Graph dataset; Graph query; Vertex array;

D O I：

10.3772/j.issn.1002-0470.2010.03.009

中图分类号：

学科分类号：

摘要：

To solve the problem of subgraph query processing in large graph databases, the paper gives a two-step node to decision feature mapping (NDFM) indexed structure, named the NDFM-Index, and based on it, proposes a subgraph query processing algorithm. The NDFM-Index uses the mapping between key nodes, with the distribution of neighbors labels, and decision features to get the indexed features which are included by query graph avoiding enumeration method. The results of theoretical analysis and experimental evaluation show that the proposed method not only avoids the enumeration method of getting subgraphs of query graph, but also effectively reduces the subgraph isomorphism tests between the query graph and graphs in candidate answer set in verification stage.

引用

页码：270 / 278

页数：8

共 16 条

[1]

Yan X., Yu P., Han J., Graph indexing: A frequent structure based approach, Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD), pp. 335-346, (2004)

[2]

Zhang S., Hu M., Yang J., TreePi: A novel graph indexing method, Proceedings of the 23nd International Conference on Data Engineering (ICDE), pp. 966-975, (2007)

[3]

Cheng J., Ke Y., Ng W., Et al., FG-Index: Towards verification free query processing on graph databases, Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD), pp. 857-872, (2007)

[4]

Zhao P., Yu J., Yu P., Graph indexing: Tree + Delta > = Graph, Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB), pp. 938-949, (2007)

[5]

Yan X., Yu P., Han J., Substructure similarity search in graph databases, Proceedings of the ACM Special Interest Group on Management of Data (SIGMOD), pp. 766-777, (2005)

[6]

Yan X., Zhu F., Han J., Et al., Searching substructures with superimposed distance, Proceedings of the 22nd International Conference on Data Engineering (ICDE), (2006)

[7]

Shasha D., Wang J., Giugno R., Algorithmic and applications of tree and graph searching, Proceedings of the Principles of Database Systems (PODS), pp. 39-52, (2002)

[8]

He H., Singh A., Closure-tree: An index structure for graph queries, Proceedings of the 22nd International Conference on Data Engineering (ICDE), pp. 38-47, (2006)

[9]

Williams D., Huan J., Wang W., Graph database indexing using structured graph decomposition, Proceedings of the 23nd International Conference on Data Engineering (ICDE), pp. 976-985, (2007)

[10]

Jiang H., Wang H., Yu P., Et al., GString: A novel approach for efficient search in graph databases, Proceedings of the 23nd International Conference on Data Engineering (ICDE), pp. 566-575, (2007)

← 1 2 →