Pervasive parallelism in data mining: dataflow solution to co-clustering large and sparse Netflix data

ABSTRACT

All Netflix Prize algorithms proposed so far are prohibitively costly for large-scale production systems. In this paper, we describe an efficient dataflow implementation of a collaborative filtering (CF) solution to the Netflix Prize problem [1] based on weighted coclustering [5]. The dataflow library we use facilitates the development of sophisticated parallel programs designed to fully utilize commodity multicore hardware, while hiding traditional difficulties such as queuing, threading, memory management, and deadlocks.

The dataflow CF implementation first compresses the large, sparse training dataset into co-clusters. Then it generates recommendations by combining the average ratings of the co-clusters with the biases of the users and movies. When configured to identify 20x20 co-clusters in the Netflix training dataset, the implementation predicted over 100 million ratings in 16.31 minutes and achieved an RMSE of 0.88846 without any fine-tuning or domain knowledge. This is an effective real-time prediction runtime of 9.7 us per rating which is far superior to previously reported results. Moreover, the implemented co-clustering framework supports a wide variety of other large-scale data mining applications and forms the basis for predictive modeling on large, dyadic datasets [4, 7].

REFERENCES

• 1: Netflix inc. netflix data. http://www.netflixprize.com//download, Oct 2006.
• 2: Pervasive software inc. pervasive data rush. http://www.pervasivedatarush.com/downloads, 2007.
• 3: Timely development. netflix prize. http://www.timelydevelopment.com/demos/NetflixPrize.aspx, 2007.
• 4: Deepak Agarwal , Srujana Merugu, Predictive discrete latent factor models for large scale dyadic data, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281199]
• 5: Arindam Banerjee , Inderjit Dhillon , Joydeep Ghosh , Srujana Merugu , Dharmendra S. Modha, A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation, The Journal of Machine Learning Research, 8, p.1919-1986, 12/1/2007
• 6: Robert Bell , Yehuda Koren , Chris Volinsky, Modeling relationships at multiple scales to improve accuracy of large recommender systems, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281206]
• 7: Meghana Deodhar , Joydeep Ghosh, A framework for simultaneous co-clustering and learning from complex data, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281222]
• 8: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, A divisive information theoretic feature clustering algorithm for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 9: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 10: Thomas George , Srujana Merugu, A Scalable Collaborative Filtering Framework Based on Co-Clustering, Proceedings of the Fifth IEEE International Conference on Data Mining, p.625-628, November 27-30, 2005 [doi>10.1109/ICDM.2005.14]
• 11: G. Golub and C. V. Loan. Matrix Computations. John Hopkins University Press, Baltimore, 1996.
• 12: A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing. Addison-Wesley, 2003.
• 13: K. Irwin and M. Walker. Four Paths to Java Parallelism., volume 13. Java Developer.s Journal, 2008.
• 14: G. Kahn. The semantics of a simple language for parallel programming. Proc. of the IFIP Congress 74, North-Holland Publishing Co., Holland, 1974.
• 15: Yehuda Koren, Factorization meets the neighborhood: a multifaceted collaborative filtering model, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401944]
• 16: E. Lee and T. Parks. Dataflow process networks. Proceedings of the IEEE, 83(5):773--801, May 1995.
• 17: B. Sarwar, G. Karypis, J. Konstan, and J. Riedl. Application of dimensionality reduction in recommender system - a case study. Proc. WebKDD'00, 2000.
• 18: S.Funk. Netflix update: Try this at home. http://sifter.org/ simon/journal/20061211.html, 2006.
• 19: Yunhong Zhou , Dennis Wilkinson , Robert Schreiber , Rong Pan, Large-Scale Parallel Collaborative Filtering for the Netflix Prize, Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management, p.337-348, June 23-25, 2008, Shanghai, China [doi>10.1007/978-3-540-68880-8_32]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Performance

Keywords:
co-clustering, dataflow, predictive modeling, scalability