Enumeration of Maximally Frequent Ordered Tree Patterns with Height-constrained Variables for Trees

• Item type: Trans(1)
• 公開日: 2019-12-23
• タイトル: Enumeration of Maximally Frequent Ordered Tree Patterns with Height-constrained Variables for Trees
• タイトル / 言語: en
• タイトル: Enumeration of Maximally Frequent Ordered Tree Patterns with Height-constrained Variables for Trees
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] ordered tree pattern, height-constrained variable, enumeration, tree structured feature, maximal frequency
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Information Sciences, Hiroshima City University
• 著者所属: Graduate School of Information Sciences, Hiroshima City University
• 著者所属: Faculty of Contemporary Business, Kyushu International University
• 著者所属: Graduate School of Information Sciences, Hiroshima City University
• 著者所属: Faculty of Science, Tokai University
• 著者所属: Computer Centre, Gakushuin University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Contemporary Business, Kyushu International University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Hiroshima City University
• 著者所属(英): en
• 著者所属(英): Faculty of Science, Tokai University
• 著者所属(英): en
• 著者所属(英): Computer Centre, Gakushuin University
• 著者名: Yusuke, Suzuki; Tetsuhiro, Miyahara; Takayoshi, Shoudai; Tomoyuki, Uchida; Satoshi, Matsumoto; Tetsuji, Kuboyama
• 著者名(英): Yusuke, Suzuki; Tetsuhiro, Miyahara; Takayoshi, Shoudai; Tomoyuki, Uchida; Satoshi, Matsumoto; Tetsuji, Kuboyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We propose height-constrained ordered tag tree patterns for representing characteristic tree structured features of structured data which are represented by rooted trees with ordered children. Height-constrained ordered tag tree patterns are ordered tree patterns having height-constrained structured variables, wildcards, tags and keywords as edge labels. For two positive integers i and j (i ≤ j), an (i,j)-height-constrained structured variable can be replaced with any rooted ordered tree whose trunk length is at least i and whose height is at most j. A height-constrained variable can represent the distance between subtree patterns connected by the variable as one of tree structured features. On the other hand, a variable without height constraint can be replaced with any rooted ordered tree. A variable without height constraint can represent the connectedness but not the distance between subtree patterns. In this sense, ordered tree patterns with height-constrained variables are more accurate tree structured features than ordered tree patterns having variables without height constraint. In this paper, first, we state that it is hard to compute an optimum frequent height-constrained ordered tag tree pattern. Then, we present an algorithm for enumerating all maximally frequent height-constrained ordered tag tree patterns. Finally, we report experimental results showing the effectiveness of the proposed model of characteristic tree structured features, maximally frequent height-constrained ordered tag tree patterns, compared with the previous model of maximally frequent ordered tag tree patterns without height constraint.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose height-constrained ordered tag tree patterns for representing characteristic tree structured features of structured data which are represented by rooted trees with ordered children. Height-constrained ordered tag tree patterns are ordered tree patterns having height-constrained structured variables, wildcards, tags and keywords as edge labels. For two positive integers i and j (i ≤ j), an (i,j)-height-constrained structured variable can be replaced with any rooted ordered tree whose trunk length is at least i and whose height is at most j. A height-constrained variable can represent the distance between subtree patterns connected by the variable as one of tree structured features. On the other hand, a variable without height constraint can be replaced with any rooted ordered tree. A variable without height constraint can represent the connectedness but not the distance between subtree patterns. In this sense, ordered tree patterns with height-constrained variables are more accurate tree structured features than ordered tree patterns having variables without height constraint. In this paper, first, we state that it is hard to compute an optimum frequent height-constrained ordered tag tree pattern. Then, we present an algorithm for enumerating all maximally frequent height-constrained ordered tag tree patterns. Finally, we report experimental results showing the effectiveness of the proposed model of characteristic tree structured features, maximally frequent height-constrained ordered tag tree patterns, compared with the previous model of maximally frequent ordered tag tree patterns without height constraint.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 12, 号 3, p. 78-88, 発行日 2019-12-23
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会