As digital video data becomes more pervasive, mining information from multimedia data becomes increasingly important. Although researches in multimedia mining area have shown great potential in daily life, the huge computational requirement prohibits its wide use in practice. Since our personal computer is shifting from uniprocessors to multicore processors, exploiting thread level parallelism in multimedia mining applications is critical to utilize the hardware resources and accelerate the mining process. This paper presents three different parallel approaches (task level, data slicing and hybrid parallel) to parallelize one widely used application in video mining system. The hybrid scheme, with the exploration of data level and task level parallelism, delivers much better performance than other two schemes. We get 10x performance improvement on a 16-way multiprocessor system. Besides, we perform several efficient optimization techniques, such as subexpression optimization, SIMD, and data blocking, to improve the performance by more than 60%. Therefore, our parallelization and optimization of the application makes it 16x faster than it used to be. Our study shows that with proper parallelization and optimization, multimedia mining can be used widely in our daily life soon.