A Compact FP-Tree for Fast Frequent Pattern Retrieval

A Compact FP-tree for Fast Frequent Pattern Retrieval Tri Thanh Nguyen Vietnam National University, Hanoi (VNUH) University of Engineering and Technology (UET) ntthanh@vnu.edu.vn Abstract Frequent patterns are useful in many data mining problems including query suggestion. Frequent patterns can be mined through frequent pattern tree (FP- tree) data structure which is used to store the compact (or compressed) representation of a transaction database (Han, et al, 2000). In this paper, we propose an algorithm to compress frequent pattern set into a smaller one, and store the set in a modified version of FP-tree (called compact FP-tree) as an inverted indexing of patterns for later quick retrieval (for query suggestion). With the compact FP-tree, we can also restore the original frequent pattern set. Our experiment results show that our compact FP-tree has a very good compression ratio, especially on sparse dataset which is the nature of query log. 1 Introduction Frequent pattern mining is an important task because its results can be used in a wide range of mining tasks, such as association rule, correlation, causality, sequential pattern, etc. as reviewed by Han (2000). In some mining tasks (e.g. association rule, correlation, or causality), frequent patterns are used as intermediate data for computing final results, so there is no need to access these patterns again. However, in some other tasks, such as query suggestion (or query recommendation) (Li, 2008), when a user enter a keyword, the search engine will recommend the potential phrases (or patterns) the user may want to use, in order to: (a) save time for users, (b) make the convenience of use, and even (c) guide the user in case he/she is not sure about what to search for. In such tasks, we need to frequently search for frequent patterns containing a certain keyword (or phrase), hence, we want to have a method that supports quick retrieval of patterns. In information retrieval, one of the contemporary methods for fast retrieval of documents containing a certain word (or phrase) is inverted indexing (Manning, et al, 2008), which manages a mapping from a keyword to a set of documents containing it. Thus, given a keyword, we will quickly have the list of related documents. We found that FP-tree can be used as an inverted indexing which can provide us a list of patterns containing a certain item. Thus, we propose to modify FP-tree to store the frequent patterns for later fast retrieval. The difference between our FP-tree and the original one is: • The original FP-tree stores the compact version of a transaction database, and an algorithm (called FP-growth) is used to find out the frequent patterns; • Our FP-tree stores the frequent patterns for quick access, so each path in the tree is already a pattern. Since the number of frequent patterns generated from a transaction database can be very large, we propose an algorithm to compress them into a much smaller (compact) set and store in FP-tree data structure. We also propose to modify related algorithms to make …

Content truncated to 500 words