Cut-and-stitch

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cut-and-stitch: efficient parallel learning of linear dynamical systems on smps

Full text

Pdf (825 KB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Las Vegas, Nevada, USA

SESSION: Research papers table of contents

Pages 471-479

Year of Publication: 2008

ISBN:978-1-60558-193-4

Authors

Lei Li	Carnegie Mellon University, Pittsburgh, PA, USA
Wenjie Fu	Carnegie Mellon University, Pittsburgh, PA, USA
Fan Guo	Carnegie Mellon University, Pittsburgh, PA, USA
Todd C. Mowry	Carnegie Mellon University, Pittsburgh, PA, USA
Christos Faloutsos	Carnegie Mellon University, Pittsburgh, PA, USA

Sponsors

ACM: Association for Computing Machinery
SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 172, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1401890.1401949 What is a DOI?

ABSTRACT

Multi-core processors with ever increasing number of cores per chip are becoming prevalent in modern parallel computing. Our goal is to make use of the multi-core as well as multi-processor architectures to speed up data mining algorithms. Specifically, we present a parallel algorithm for approximate learning of Linear Dynamical Systems (LDS), also known as Kalman Filters (KF). LDSs are widely used in time series analysis such as motion capture modeling, visual tracking etc. We propose Cut-And-Stitch (CAS), a novel method to handle the data dependencies from the chain structure of hidden variables in LDS, so as to parallelize the EM-based parameter learning algorithm. We implement the algorithm using OpenMP on both a supercomputer and a quad-core commercial desktop. The experimental results show that parallel algorithms using Cut-And-Stitch achieve comparable accuracy and almost linear speedups over the serial version. In addition, Cut-And-Stitch can be generalized to other models with similar linear structures such as Hidden Markov Models (HMM) and Switching Kalman Filters (SKF).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
	2	Gregory Buehrer , Srinivasan Parthasarathy , Shirish Tatikonda , Tahsin Kurc , Joel Saltz, Toward terabyte pattern mining: an architecture-conscious solution, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229432]
	3	E. Chang, K. Zhu, H. Wang, H. Bai, J. Li, Z. Qiu, and H. Cui. Parallelizing support vector machines on distributed computers. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, NIPS 20, pages 257--264. MIT Press, 2007.
	4	C.-T. Chu, S. K. Kim, Y.-A. Lin, Y. Yu, G. R. Bradski, A. Y. Ng, and K. Olukotun. Map-reduce for machine learning on multicore. In B. Schölkopf, J. C. Platt, and T. Hoffman, editors, NIPS 19, pages 281--288. MIT Press, 2006.
	5	R. Collobert, S. Bengio, and Y. Bengio. A Parallel Mixture of SVMs for Very Large Scale Problems. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, NIPS. MIT Press, 2002.
	6	Christopher B. Colohan , Anastassia Ailamaki , J. Gregory Steffan , Todd C. Mowry, Tolerating Dependences Between Large Speculative Threads Via Sub-Threads, Proceedings of the 33rd annual international symposium on Computer Architecture, p.216-226, June 17-21, 2006
	7	Shengnan Cong , Jiawei Han , David Padua, Parallel mining of closed sequential patterns, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081937]
	8	Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
	9	H. P. Graf, E. Cosatto, L. Bottou, I. Dourdanovic, and V. Vapnik. Parallel support vector machines: The cascade SVM. In NIPS 17, 2004.
	10	Intel. Intel research advances 'era of tera': www.intel.com/pressroom/archive/releases/20070204comp.htm.
	11	L. Li, J. McCann, C. Faloutsos, and N. Pollard. Laziness is a virtue: Motion stitching using effort minimization. In Short Papers Proceedings of EUROGRAPHICS, 2008.
	12	Colby Ranger , Ramanan Raghuraman , Arun Penmetsa , Gary Bradski , Christos Kozyrakis, Evaluating MapReduce for Multi-core and Multiprocessor Systems, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.13-24, February 10-14, 2007 [doi>10.1109/HPCA.2007.346181]
	13	S. Reinhardt and G. Karypis. A multi-level parallel implementation of a program for finding frequent patterns in a large sparse graph. In IPDPS, pages 1--8. IEEE, 2007.