Polynomial Time Pattern Matching Algorithm for Ordered Graph Patterns
详细信息 查看全文
- 作者：Takahiro Hino (21)
Yusuke Suzuki (21)
Tomoyuki Uchida (21)
Yuko Itokawa (22) - 刊名：Lecture Notes in Computer Science
- 出版年：2013
- 出版时间：2013
- 年：2013
- 卷：7842
- 期：1
- 页码：102-115
- 全文大小：1026KB
- 参考文献：1. Angluin, D.: Inductive inference of formal languages from positive data. Information and Control?45(2), 117-35 (1980) CrossRef
2. Horváth, T., Ramon, J., Wrobel, S.: Frequent subgraph mining in outerplanar graphs. Data Mining and Knowledge Discovery?21(3), 472-08 (2010) CrossRef
3. Jiang, X., Bunke, H.: On the coding of ordered graphs. Computing?61(1), 23-8 (1998) CrossRef
4. Kawamoto, S., Suzuki, Y., Shoudai, T.: Learning characteristic structured patterns in rooted planar maps. In: IMECS 2010, IAENG, pp. 465-70 (2010)
5. Kononenko, I., Kukar, M.: Machine Learning and Data Mining: Introduction to Principles and Algorithms. Horwood Pub. (2007)
6. Kuramochi, M., Karypis, G.: Discovering frequent geometric subgraphs. Information Systems?32(8), 1101-120 (2007) CrossRef
7. Michalski, R.S., Bratko, I., Bratko, A. (eds.): Machine Learning and Data Mining; Methods and Applications. John Wiley & Sons, Inc., NY (1998)
8. Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Goto, E., Furukawa, K., Nakajima, R., Nakata, I., Yonezawa, A. (eds.) RIMS 1982. LNCS, vol.?147, pp. 115-27. Springer, Heidelberg (1983) CrossRef
9. Shoudai, T., Uchida, T., Miyahara, T.: Polynomial time algorithms for finding unordered tree patterns with internal variables. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol.?2138, pp. 335-46. Springer, Heidelberg (2001) CrossRef
10. Suzuki, Y., Shoudai, T., Uchida, T., Miyahara, T.: Ordered term tree languages which are polynomial time inductively inferable from positive data. Theoretical Computer Science?350(1), 63-0 (2006) CrossRef
11. Takami, R., Suzuki, Y., Uchida, T., Shoudai, T.: Polynomial time inductive inference of TTSP graph languages from positive data. IEICE Transactions?92-D(2), 181-90 (2009)
12. Uchida, T., Itokawa, Y., Shoudai, T., Miyahara, T., Nakamura, Y.: A new framework for discovering knowledge from two-dimensional structured data using layout formal graph system. In: Arimura, H., Sharma, A.K., Jain, S. (eds.) ALT 2000. LNCS (LNAI), vol.?1968, pp. 141-55. Springer, Heidelberg (2000) CrossRef
13. Tutte, W.T.: A census of planar maps. Canadian Journal of Mathematics?15, 249-71 (1963) CrossRef
14. Yamasaki, H., Sasaki, Y., Shoudai, T., Uchida, T., Suzuki, S.: Learning block-preserving graph patterns and its application to data mining. Machine Learning?76(1), 137-73 (2009) CrossRef
15. Yoshimura, Y., Shoudai, T., Suzuki, Y., Uchida, T., Miyahara, T.: Polynomial time inductive inference of cograph pattern languages from positive data. In: Muggleton, S.H., Tamaddoni-Nezhad, A., Lisi, F.A. (eds.) ILP 2011. LNCS, vol.?7207, pp. 389-04. Springer, Heidelberg (2012) CrossRef - 作者单位：Takahiro Hino (21)
Yusuke Suzuki (21)
Tomoyuki Uchida (21)
Yuko Itokawa (22)
21. Department of Intelligent Systems, Hiroshima City University, Japan
22. Faculty of Psychological Science, Hiroshima International University, Japan - ISSN：1611-3349
文摘
Ordered graphs, each of whose vertices has a unique order on edges incident to the vertex, can represent graph structured data such as Web pages, $\mbox{\TeX}$ ?sources, CAD and MAP. In this paper, in order to design computational machine learning for such data, we propose an ordered graph pattern with ordered graph structures and structured variables. We define an ordered graph language for an ordered graph pattern g as the set of all ordered graphs obtained from g by replacing structured variables in g with arbitrary ordered graphs. We present a polynomial time pattern matching algorithm for determining whether or not a given ordered graph is contained in the ordered graph language for a given ordered graph pattern. We also implement the proposed algorithm on a computer and evaluate the algorithm by reporting and discussing experimental results.