Development of efficient knowledge discovery systems for large semistructured data

点击翻译按钮获取中文摘要

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.