2008 CutandStitchEfficientParallelLe

• (Li et al., 2008) ⇒ Lei Li, Wenjie Fu, Fan Guo, Todd C. Mowry, and Christos Faloutsos. (2008). “Cut-and-stitch: Efficient Parallel Learning of Linear Dynamical Systems on Smps.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401949

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Cut-and-stitch%3A+efficient+parallel+learning+of+linear+dynamical+systems+on+smps%22+2008
• http://portal.acm.org/citation.cfm?doid=1401890.1401949&preflayout=flat#citedby

Quotes

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

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 CutandStitchEfficientParallelLe	Christos Faloutsos Lei Li Fan Guo Wenjie Fu Todd C. Mowry			Cut-and-stitch: Efficient Parallel Learning of Linear Dynamical Systems on Smps				10.1145/1401890.1401949