A Parallel Algorithm Based on Prefix Tree for Sequence Pattern Mining

Author

Ren, Jia-dong ; Dong, Yuan ; He, Hai-tao

Author_Institution

Coll. of Inf. Sci. & Eng., YanShan Univ., Qinhuangdao, China

fYear

2010

fDate

23-24 Oct. 2010

Firstpage

6

Lastpage

11

Abstract

Algorithm PTPSPM (a parallel algorithm based on prefix tree for sequence pattern mining) is proposed in order to deal with the speed limited and effectiveness problem of the sequence pattern mining in massive data. In this paper, a new prefix-tree structure and an improved prefix-span algorithm are introduced to mine the local sequence, the global sequence are obtained by merging all the local sequences. A new prefix tree pruning technique is presented to delete the global k-sequence which can not be attended. PTPSPM algorithm applies project database identifier index table of dynamic scheduling to avoid the processor idle waiting. Additionally, it cites selective sampling techniques to balance the loads between processors. The experiment results demonstrate that PTPSPM algorithm has better execution performance and speedup.

Keywords

data mining; parallel algorithms; tree data structures; PTPSPM; dynamic scheduling; parallel algorithm; prefix tree pruning technique; prefix-span algorithm; processor idle waiting; project database identifier index table; sequence pattern mining; Algorithm design and analysis; Data mining; Databases; Heuristic algorithms; Load management; Parallel algorithms; Silicon; global sequence; local sequence; parallel mining; prefix-tree; sequence mining;

fLanguage

English

Publisher

ieee

Conference_Titel

Cryptography and Network Security, Data Mining and Knowledge Discovery, E-Commerce & Its Applications and Embedded Systems (CDEE), 2010 First ACIS International Symposium on

Conference_Location

Qinhuangdao

Print_ISBN

978-1-4244-9595-5

Type

conf

DOI

10.1109/CDEE.2010.10

Filename

5759406