Design of the fast computable similarities for tree-structured data and their extension to several discrete structures

树结构数据的快速可计算相似性的设计及其对多个离散结构的扩展

• 批准号: 21500145
• 负责人: HIRATA Kouichi
• 金额: $ 2.83万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500145/
• 关键词: 木構造の類似度; 木の編集距離; 順序木; 無順序木; 局所頻度距離; 二分木符号; 木カーネル; 木包含問題; 木; 木の類似度・非類似度; 編集距離; 二分木コード; ボトムアップ編集距離; 系統樹; エピソード; データマイニング; 有向グラフ

This research introduced a new hierarchy of the tree edit distance and improved both the MAXSNP-hardness of computing the unordered tree edit distance and the time complexity for the tractable variations of it. Also it introduced both the local frequency distance, which runs in linear time, with constant factor lower bound of the ordered tree edit distance and the string edit distance of binary tree codes, which runs in quadratic time, with both the constant factor lower bound and the upper bound. Furthermore, it designed the tree kernel based on them.

本文提出了一种新的树编辑距离的层次结构，改进了计算无序树编辑距离的MAXSNP困难度和无序树编辑距离易处理变化的时间复杂度，并引入了有序树编辑距离的常数因子下界的线性时间局部频率距离和二次时间二叉树编码的字符串编辑距离，同时具有常数因子下限和上限。并在此基础上设计了树核。

项目成果

Improved MAX SNP-Hard Results for Finding an Edit Distances between Unordered Trees

改进了查找无序树之间编辑距离的 MAX SNP-Hard 结果

• DOI: 10.1007/978-3-642-21458-5_34
• 发表时间: 2011
• 期刊: Lecture Notes in Computer Science (Proc.CPM'11)
• 作者: K.Hirata;Y.Yamamoto;T.Kuboyama
• 通讯作者: T.Kuboyama

Mining Frequent k-Partite Episodes from Event Sequences, New Frontiers in Artificial Intelligence

从事件序列中挖掘频繁的 k 部分片段，人工智能的新领域

• 发表时间: 2010
• 期刊: Lecture Notes in Artificial Intelligence
• 作者: T. Katoh;H. Arimura;K. Hirata
• 通讯作者: K. Hirata

Mining Frequent Bipartite Episodes from Event Sequences, Proc

从事件序列中挖掘频繁的二分情节，Proc

• 发表时间: 2009
• 期刊: 12th International Conference on Discovery Science(DS2009), Lecture Notes in Artificial Intelligence
• 作者: T. Katoh;H. Arimura;K. Hirata
• 通讯作者: K. Hirata

ラベル付き根付き順序木のボトムアップ距離

标记有根有序树的自底向上距离

• 发表时间: 2010
• 作者: 山本恭之;平田耕一;林田崇佑;久保山哲二
• 通讯作者: 久保山哲二

自由度1及び2の分割自由カーネル

具有 1 和 2 自由度的自由分割内核

• 发表时间: 2010
• 作者: 申吉浩;久保山哲二
• 通讯作者: 久保山哲二