Development of efficient knowledge discovery systems for large semistructured data

随着Internet和Web服务技术的飞速发展，出现了一种新的海量数据--半结构化数据，半结构化数据是指Web页面和XML文档等弱结构化电子数据的集合。本课题研究了面向大规模半结构化数据的高效知识发现系统。我们的主要贡献之一是关于树的内核。我们引入了一个新的核函数的标记有序树，并显示了一个硬度的结果，在设计更一般的标记树的树核（JSAI最佳论文奖，2006年）。另一个重要的是情节挖掘。我们证明了一个情节是无并行的当且仅当它是串行建设性的。接下来，我们研究了半结构化数据的实际处理方法，如模式匹配，文本压缩和索引结构。本文的主要工作如下：基于单向序贯处理的思想，设计了有效的路径模式匹配算法。与XMLTK相比，这些算法运行速度快2 - 6倍，空间效率高6倍。我们还提出了一个高效的索引结构，快速可达性测试的有向图，并实现了它（DEWS 2007年最佳论文奖）。在此基础上，我们提出了一种新的压缩模式匹配（CPM）算法，与BPE型CPM算法相比，该算法在压缩率和搜索时间上都有较大的提高。最后，我们将本课题的理论和实践成果应用到知识发现系统中。我们证明了这些应用程序在生物信息学，制药，音乐，交通和安全等各个领域有效地工作。

By the rapid progress of Internet and Web service technologies, a new kind of massive data called semistructured data emerged, where a semistructured data is a collection of weakly structured electronic data such as Web pages and XML documents. In this research project, we studied efficient knowledge discovery systems for large semistructured data.First we studied theoretical foundations of learning and discovery for semistructured data. One of our main contributions is on kernels for trees. We introduced a new kernel function for labeled ordered trees and showed a hardness result in designing tree kernels for more general labeled trees(JSAI Best Paper Award in 2006). Another important one is on episode mining. We showed that an episode is parallel-free if and only if it is serially constructive.Next, we studied practical processing methods for semistructured data such as pattern matching, text compression, and index structures. Main contributions are as follows We devised efficient matching algorithms for path patterns based on the one-way sequential processing. These algorithms run 2 - 6 times faster and 6 times space-efficient in comparison with XMLTK. We also proposed an efficient index structure for the fast reachability test on directed graphs and implemented it(DEWS2007 BestPaper Award). Furthermore, we developed a new compressed pattern matching(CPM) algorithm that improves both the compression ratio and the search time ratio in comparison with a BPE type CPM algorithm.Finally, we applied the theoretical and practical results in this project to knowledge discovery systems. We demonstrated that these applications work effectively in various areas such as bioinformatics, pharmacy, music, traffic, and security.