• Article
  • | |
  • Metrics
  • |
  • Reference [20]
  • |
  • Related [20]
  • |
  • Cited by [3]
  • | |
  • Comments
    Abstract:

    Abstract: This paper proposes an approach for subgraph isomorphism testing from a set of priori given small graphs to a large graph issued on-line. In order to reduce the computational cost,based on DFS Code,an elaborate organization of a set of graphs is presented,and a look-ahead-pruning based algorithm of subgraph isomorphism testing from multiple small graphs to a large graph is proposed.Moreover, an index technique based on data miningis introduced.Analytical and experimental results show the on-line computational cost of the proposed method is much less than the state-of-the-art method and it is about one order of magnitude faster than the existing method with more than one order of magnitude less off-line construction time.

    Reference
    [1] Conte D, Foggia P, Sansone C, Vento M. Thirty years of graph matching in pattern recognition. Int’l Journal of Pattern Recognitionand Artificial Intelligence,2004,18(3):265?298.
    [2] Cordella LP, Foggia P, Sansone C, Vento M. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. onPattern Analysis and Machine Intelligence, 2004,26(10):1367?1372.
    [3] Ullmann JR. An algorithm for subgraph isomorphism. Journal of the ACM, 1976,23(1):31?42.
    [4] Sengupta K, Boyer KL. Organizing large structural modelbases. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1995,17(4):321?332.
    [5] Messmer BT, Bunke H. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition, 1999,32(12):1979?1998.
    [6] Messmer BT, Bunke H. Efficient subgraph isomorphism detection: A decomposition approach. IEEE Trans. on Knowledge andData Engineering, 2000,12(2):307?323.
    [7] Chen C, Yan X, Yu PS, Han J, Zhang DQ, Gu X. Towards graph containment search and indexing. In: Koch C, Gehrke J,Garofalakis MN, Srivastava D, Aberer K, Deshpande A,Florescu D, Chan CY, Ganti V, Kanne CC, Klas W, Neuhold EJ, eds. Proc.of the Int’l Conf. on Very Large Data Bases. Vienna: ACM, 2007. 926?937.
    [8] Zhou SG, Yu ZC, Jiang HL. Concepts, issues, and advances of searching in graph-structured data. Communications of the ChinaComputer Federation, 2007,3(8):59?65 (in Chinese with English abstract).
    [9] Yan X, Yu PS, Han J. Graph indexing: A frequent structure-based approach. In: Weikum G, Konig AC, Dessloch S, eds. Proc. ofthe ACM SIGMOD Int’l Conf. on Management of Data. Paris: ACM, 2004. 335?346.
    [10] Cheng J, Ke Y, Ng W, Lu A. FG-Index: Towards verification-free query processing on graph databases. In: Chan CY, Ooi BC,Zhou A, eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data. Beijing: ACM, 2007. 857?872.
    [11] Washio T, Motoda H. State of the art of graph-based data mining. SIGKDD Explorations, 2003,5(1):59?68.
    [12] Yan X, Han J. gSpan: Graph-Based substructure pattern mining. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the IEEE Int’lConf. on Data Mining. Maebashi City:IEEE, 2002. 721?724.
    [13] Wang W, Zhou HF, Yuan QQ, Lou YB, Shi BL. Mining frequent patterns based on graph theory. Journal of Computer Researchand Development, 2005,42(2):230?235 (in Chinese with English abstract).
    [14] Li XT, Li JZ, Gao H. An efficient frequent subgraph mining algorithm. Journal of Software, 2007,18(10):2469?2480 (in Chinesewith English abstract).http://www.jos.org.cn/1000-9825/18/2469.htm
    [15] Liu Y, Li J, Gao H. Summarizing graph patterns. In: Bernstein P, Bertino E, Dayal U, Lockemann P, Weikum G, Whang KY, eds.Proc. of the IEEE Int’l Conf. on Data Mining. Cancun: IEEE, 2008. 903?912.
    [16] Fürer M, Raghavachari B. Approximating the minimum degree spanning tree to within one from the optimal degree. In: Smithies M,ed. Proc. of the ACM/SIGACT-SIAM Symp. on Discrete Algorithms. Orlando: SIAM, 1992. 317?324.
    [17] Tatarinov I, Viglas S, Beyer KS, Shanmugasundaram J, Shekita EJ, Zhang C. Storing and querying ordered XML using a relational database system. In: Franklin MJ, Moon B, Ailamaki A, eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data.Madison: ACM, 2002. 204?215.
    附中文参考文献: [8] 周水庚,蔚赵春,蒋豪良.图结构数据搜索的概念、问题与进展.中国计算机学会通讯,2007,3(8):59?65.
    [13] 汪卫,周皓峰,袁晴晴,楼宇波,施伯乐.基于图论的频繁模式挖掘.计算机研究与发展,2005,42(2):230?235.
    [14] 李先通,李建中,高宏.一种高效频繁子图挖掘算法.软件学报,2007,18(10):2469?2480. http://www.jos.org.cn/1000-9825/18/2469.htm
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张硕,李建中,高宏,邹兆年.一种多到一子图同构检测方法.软件学报,2010,21(3):401-414

Copy
Share
Article Metrics
  • Abstract:8003
  • PDF: 10619
  • HTML: 0
  • Cited by: 0
History
  • Received:July 17,2008
  • Revised:October 09,2008
You are the first2032327Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063