Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

A MapReduce Reinforced Distributed Sequential Pattern Mining Algorithm

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 9529))

  • 1484Accesses

Abstract

Redesign and reimplementation of traditional sequential pattern mining algorithms on distributed computing frameworks are essential for dealing with big data. Along the way, the critical issue is how to minimize the communication overhead of the distributed sequential pattern mining algorithm and maximize its execution efficiency by balancing the workload of distributed computing resources. To address such an issue, this paper proposes a MapReduce reinforced distributed sequential pattern mining algorithm DGSP (Distributed GSP algorithm based on MapReduce), which consists of two MapReduce jobs. The “two-jobs” structure of DGSP can effectively reduce the communication overhead of the distributed sequential pattern mining algorithm. DGSP also enables optimizing the workload balance and the execution efficiency of distributed sequential pattern mining by evenly partitioning the database and assigning the fragments to Map workers. Experimental results indicate that DGSP can significantly improve the overall performance, scalability and fault tolerance of sequential pattern mining on big data.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. Han, J., Pei, J., Yan, X.: Sequential pattern mining by pattern-growth: principles and extension. Found. Adv. Data Min.180, 183–220 (2005)

    Article MATH  Google Scholar 

  2. Dean, J., et al.: MapReduce: simplified data processing on large clusters. Commun. ACM51(1), 107–113 (2008)

    Article  Google Scholar 

  3. Groot, S., Goda, K., Kitsuregawa, M.: A study on workload imbalance issues in data intensive distributed computing. In: Kikuchi, S., Sachdeva, S., Bhalla, S. (eds.) DNIS 2010. LNCS, vol. 5999, pp. 27–32. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  4. Sarma, A.D., Afrati, F.N., Salihoglu, S., et al.: Upper and lower bounds on the cost of a map-reduce computation. In: Proceedings of the VLDB Endowment, pp. 277–288 (2013)

    Google Scholar 

  5. Guralnik, V., Garg, N., Karypis, G.: Parallel tree projection algorithm for sequence mining. In: Sakellariou, R., Keane, J.A., Gurd, J.R., Freeman, L. (eds.) Euro-Par 2001. LNCS, vol. 2150, pp. 310–320. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Huang, J.-W., Lin, S.-C., Chen, M.-S.: DPSP: distributed progressive sequential pattern mining on the cloud. In: Zaki, M.J., Yu, J.X., Ravindran, B., Pudi, V. (eds.) PAKDD 2010. LNCS, vol. 6119, pp. 27–34. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  7. Chen, C.C., Tseng, C.Y., Chen, M.S.: Highly scalable sequential pattern mining based on MapReduce model on the cloud. In: 2013 IEEE International Congress on Big Data, pp. 310–317 (2013)

    Google Scholar 

  8. Yu, D., Wu, W., Zheng, S., Zhu, Z.: BIDE-based parallel mining of frequent closed sequences with MapReduce. In: Xiang, Y., Stojmenovic, I., Apduhan, B.O., Wang, G., Nakano, K., Zomaya, A. (eds.) ICA3PP 2012, Part II. LNCS, vol. 7440, pp. 177–186. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  9. Wei, Y.Q., Liu, D., Duan, L.S.: Distributed PrefixSpan algorithm based on MapReduce. In: 2012 International Symposium on Information Technology in Medicine and Education, pp. 901–904 (2012)

    Google Scholar 

  10. Srikant, R., Agrawal, R.: Mining sequential pattern: generalizations and performance improvements. In: Apers, P., Bouzeghoub, M., Gardarin, G. (eds.) EDBT 1996. LNCS, vol. 1057, pp. 1–17. Springer, Heidelberg (1996)

    Google Scholar 

  11. WordCount.http://wiki.apache.org/hadoop/WordCount

  12. Agrawal, R., Srikant, R.: Mining sequential pattern. In: 11th International Conference on Data Engineering, pp. 3–14 (1995)

    Google Scholar 

  13. Ayres, J., Gehrke, J., Yiu, T., et al.: Sequential pattern mining using a bitmap representation. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 429–435 (2002)

    Google Scholar 

  14. Han, J., Pei, J., Mortazavi-Asl, B., et al.: FreeSpan: frequent pattern-projected sequential pattern mining. In: Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 355–359 (2000)

    Google Scholar 

  15. Pei, J., Han, J., Pinto, H.: PrefixSpan: mining sequential pattern efficiently by prefix-projected pattern growth. In: 17th International Conference on Data Engineering, pp. 215–224 (2001)

    Google Scholar 

  16. Zaki, M.: SPADE: An efficient algorithm for mining frequent sequences. Mach. Learn.41(2), 31–60 (2001)

    Article MATH  Google Scholar 

  17. Zhang, C., Hu, K., Liu, H.: FMGSP: an efficient method of mining global sequential pattern. In: 4th International Conference on Fuzzy Systems and Knowledge Discovery, pp. 761–765 (2007)

    Google Scholar 

  18. Fang, W., Lu, M., Xiao, X., et al.: Frequent itemset mining on graphics processors. In: Proceedings of the 5th International Workshop on Data Management on New Hardware, pp. 34–42 (2009)

    Google Scholar 

  19. Hryniow, K.: Parallel pattern mining - application of GSP algorithm for graphics processing units. In: 13th International Carpathian Control Conference, pp. 233–236 (2012)

    Google Scholar 

  20. Hadoop Website.http://hadoop.apache.org/

  21. SPMF.http://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php

  22. Frequent Itemset Mining Dataset Repository.http://fimi.ua.ac.be/data/

  23. Spark Website.https://spark.apache.org/

Download references

Acknowledgments

This work is partly supported by the grants of National Natural Science Foundation of China (61572374, 61070013, 61300042, U1135005, 71401128), the Fundamental Research Funds for the Central Universities (No. 2042014kf0272, No. 2014211020201), Shanghai Knowledge Service Platform Project (ZF1213) and Natural Science Foundation of HuBei (2011CDB072).

Author information

Authors and Affiliations

  1. State Key Laboratory of Software Engineering, Computer School, Wuhan University, Wuhan, 430072, China

    Xiao Yu & Jin Liu

  2. Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, 200241, China

    Xiao Liu

  3. School of Computer Science and Information Engineering, Hubei University, Wuhan, 430062, China

    Chuanxiang Ma

  4. Economics and Management School, Wuhan University, Wuhan, 430072, China

    Bin Li

Authors
  1. Xiao Yu

    You can also search for this author inPubMed Google Scholar

  2. Jin Liu

    You can also search for this author inPubMed Google Scholar

  3. Xiao Liu

    You can also search for this author inPubMed Google Scholar

  4. Chuanxiang Ma

    You can also search for this author inPubMed Google Scholar

  5. Bin Li

    You can also search for this author inPubMed Google Scholar

Corresponding authors

Correspondence toJin Liu orXiao Liu.

Editor information

Editors and Affiliations

  1. Central South University, Changsha, China

    Guojun Wang

  2. The University of Sydney, Sydney, New South Wales, Australia

    Albert Zomaya

  3. University of Murcia, Murcia, Murcia, Spain

    Gregorio Martinez

  4. Hunan University , Changsha, China

    Kenli Li

Rights and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Yu, X., Liu, J., Liu, X., Ma, C., Li, B. (2015). A MapReduce Reinforced Distributed Sequential Pattern Mining Algorithm. In: Wang, G., Zomaya, A., Martinez, G., Li, K. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2015. Lecture Notes in Computer Science(), vol 9529. Springer, Cham. https://doi.org/10.1007/978-3-319-27122-4_13

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp