Development of efficient knowledge discovery systems for large semistructured data

随着Internet和Web服务技术的快速发展，出现了一种新的海量数据，称为半结构化数据，其中半结构化数据是Web页面和XML文档等弱结构化电子数据的集合。在本研究项目中，我们研究了大型半结构化数据的高效知识发现系统。首先研究了半结构化数据学习和发现的理论基础。我们的主要贡献之一是关于树的内核。我们为标号有序树引入了一个新的核函数，并给出了更一般标号树的树核设计的一个困难结果(2006年JSAI最佳论文奖)。另一个重要的问题是事件挖掘。其次，研究了模式匹配、文本压缩、索引结构等实用的半结构化数据处理方法。主要贡献如下：设计了基于单向顺序处理的高效路径模式匹配算法。这些算法的运行速度是XMLTK的2-6倍，空间效率是XMLTK的6倍。我们还针对有向图的快速可达性测试提出了一种高效的索引结构，并加以实现(DEWS2007 BestPaper奖)。在此基础上，提出了一种新的压缩模式匹配(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.