2024-03-19T10:14:21Z
https://repository.dl.itc.u-tokyo.ac.jp/oai
oai:repository.dl.itc.u-tokyo.ac.jp:00002419
2022-12-19T03:44:12Z
34:105:330
9:233:280
シーケンスパタマイニングの高速アルゴリズムに関する研究
Fast Algorithms for Sequential Pattern Mining
Yang, Zhenglu
6673
548
University of Tokyo (東京大学)
博士(情報理工学)
Sequential pattern mining, which extracts frequent subsequences from a sequence database, has attracted a great deal of interest during the recent surge in data mining research because it is the basis of many applications. Much work has been carried out on mining frequent patterns, however, their performance is still far from satisfactory because of two main challenges: large search spaces and the ineffectiveness in handling dense data sets. To offer a solution to the above challenges, we have proposed a series of novel algorithms, called the LAst Position INduction (LAPIN) sequential pattern mining, which is based on the idea that the last position of an item, $\alpha$, is the key to judging whether or not a frequent k-length sequential pattern can be extended to be a frequent (k+1)-length pattern by appending the item $\alpha$ to it. LAPIN can largely reduce the search space during the mining process, and is very effective in mining dense data sets. Our performance study demonstrates that LAPIN outperforms the existing state-of-the-art algorithms by up to orders of magnitude on pattern dense data sets. Moreover, in this thesis, we propose our effective Web log mining system based on our efficient sequential mining algorithm to extract user access patterns from traversal path in Web logs. Recently, the skyline query has attracted considerable attention. In this thesis, we are interested in the general model of skyline query, General Dominant Relationship. We find the interrelated connection between sequential pattern mining and the general dominant relationship. Based on this discovery, we extend sequential pattern mining techniques to efficiently answer the general dominant relationship queries. Extensive experiments illustrate the effectiveness and efficiency of our methods
thesis
2008-03
2008-03-13
application/pdf
甲第23174号
https://repository.dl.itc.u-tokyo.ac.jp/record/2419/files/48047420.pdf
eng