document: Cut-and-stitch : efficient parallel learning of linear dynamical systems on smps 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 ) .
doc_bio_tags: O O O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O