Abstract
The process of resource distribution and load balance of a distributed P2P network can be described as the process of mining Supplement Frequent Patterns (SFPs) from query transaction database. With given minimum support (min_sup) and minimum share support (min_share_sup), each SFP includes a core frequent pattern (BFP) used to draw other frequent or sub-frequent items. A latter query returns a subset of a SFP as the result. To realize the SFPs mining, this paper proposes the structure of SFP-tree along with relative mining algorithms. The main contribution includes: (1) Describes the concept of Supplement Frequent Pattern; (2) Proposes the SFP-tree along with frequency-Ascending order header table FP-Tree (AFP-Tree) and Conditional Mix Pattern Tree (CMP-Tree); (3) Proposes the SFPs mining algorithms based on SFP-Tree; and (4) Conducts the performance experiment on both synthetic and real datasets. The result shows the effectiveness and efficiency of the SFPs mining algorithm based on SFP-Tree.
This work is supported by the National Natural Science Foundation of China under Grant No. 60773169 and No. 60702075, Development Foundation of Chengdu University of Information Technology(KYTZ200811).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules. In: Proc. 1994 Int. Conf. Very Large Data Bases (VLDB 1994), Santiago, Chile, pp. 487–499 (1994)
Savasere, A., Omiecinski, E., Navathe, S.: An efficient algorithm for mining association rules in large databases. In: Proc. 1995 Int. Conf. Very Large Data Bases (VLDB 1995), Zurich, Switzerland, pp. 432–443 (1995)
Zaki, M.J., Parthasarathy, S., Ogihara, M., Li, W.: New algorithms for fast discovery of association rules. In: Proc.of the 3rd Int’l Conf. on KDD and Data Mining(KDD 1997), NewportBeach,California (August 1997)
Park, J.S., Chen, M.S., Yu, P.S.: An effective hash-based algorithm for mining association rules. In: Proceedings of ACM SIGMOD International Conference on Management of Data, San Jose, CA, pp. 175–186 (May 1995)
Han, J., Pei, J., Yin, Y.: Mining frequent patterns without candidate generation. In: Proc. 2000 ACMSIGMOD Int. Conf. Management of Data (SIGMOD 2000), Dallas, TX, pp. 1–12 (2000)
Pei, J., Han, J., Lakshmanan, L.V.S.: Mining frequent itemsets with convertible constraints. In: Proc. 2001 Int. Conf. Data Engineering (ICDE 2001), Heidelberg, Germany, pp. 332–433 (2001)
Pei, J., Han, J., Lu, H., Nishio, S., Tang, S., Yang, D.: H-Mine: Hyper-structure mining of frequent patterns in large databases. In: Proc. 2001 Int. Conf. Data Mining (ICDM 2001), San Jose, CA, pp. 441–448 (2001)
Grahne, G., Zhu, J.: Efficiently Using. Prefix-trees in Mining Frequent Itemsets. In: Proc. IEEE ICDM 2003 Workshop FIMI 2003 (Prefix(fpgrowth)) (2003)
Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., Hsu, M.-C.: PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth. In: Proc. 2001 Int. Conf. Data Engineering (ICDE 2001), Heidelberg, Germany, pp. 215–224 (2001)
Lo, D., Khoo, S.-C., Liu, C.: Efficient mining of iterative patterns for software specification discovery. In: Proc. KDD 2007, San Jose, California, USA, August, pp. 460–469 (2007)
Giannotti, F., Nanni, M., Pinelli, F., Pedreschi, D.: Trajectory pattern mining. In: KDD 2007, pp. 330–339 (2007)
CloseZaki, M.J., Hsiao, C.J.: CHARM: An efficient algorithm for closed itemset mining. In: Proc. 2002 SIAM Int. Conf. Data Mining, Arlington, VA, pp. 457–473 (2002)
ClosePasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Discovering frequent closed itemsets for association rules. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 398–416. Springer, Heidelberg (1998)
ClosePei, J., Han, J., Mao, R.: CLOSET: An efficient algorithm for mining frequent closed itemsets. In: Proc. 2000 ACM-SIGMOD Int. Workshop Data Mining and Knowledge Discovery (DMKD 2000), Dallas, TX, pp. 11–20 (2000)
Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Discovering frequent closed itemsets for association rules. In: Proceeding of the 7th International Conference on Database Theory, pp. 398–416 (1999)
maxJ. Roberto, J.B.: Efficiently mining long patterns from databases. In: Proceedings of the 1998 ACM SIGMOD international conference on Management of data, pp. 85–93 (1998)
maxLin, D.I., Kedem, Z.M.: Pincer-Search: A new algorithm for discovering the maximum frequent set. In: Schek, H.J. (ed.) Proceedings of the 6th European Conference on Extending Database Technology, pp. 105–119. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, Y., Liu, Y., Zeng, T., Xu, K., Tang, R. (2008). Mining Supplemental Frequent Patterns. In: Tang, C., Ling, C.X., Zhou, X., Cercone, N.J., Li, X. (eds) Advanced Data Mining and Applications. ADMA 2008. Lecture Notes in Computer Science(), vol 5139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88192-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-88192-6_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88191-9
Online ISBN: 978-3-540-88192-6
eBook Packages: Computer ScienceComputer Science (R0)