Phát triển các giải thuật song song trong khai phá luật kết hợp

Chia sẻ: Nguyễn Minh Vũ | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

45
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

In this paper we present two parallel algorithms for mining association rules that are well suited for distributed memory parallel computers. The algorithms are developed based on FP-growth method. The first algorithm is a task parallel formulation using a static load balancing technique. The second algorithm improves upon the first algorithm by dynamically balancing the load when the static task assignment leads to load imbalance.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phát triển các giải thuật song song trong khai phá luật kết hợp

’ Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.23, S.2 (2007), 184–200 ı e e . . a ` . ’ ’ ´ ˆ ´ ˆ PHAT TRIEN CAC GIAI THUAT SONG SONG . . ´ ´ ˆ ˆ TRONG KHAI PHA LUAT KET HO P . . ˜ ˆ NGUYEN LONG GIANG Viˆn Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nam e o e o e e e . . . . a o . . Abstract. In this paper we present two parallel algorithms for mining association rules that are well suited for distributed memory parallel computers. The algorithms are developed based on FP-growth method. The ﬁrst algorithm is a task parallel formulation using a static load balancing technique. The second algorithm improves upon the ﬁrst algorithm by dynamically balancing the load when the static task assignment leads to load imbalance. We use the count matrix technique to compute the weight of tasks and to distribute tasks to processors. This technique also helps to reduce the time needed to scan the trees and to reduce communication cost. We also use the hash tree technique to group similar preﬁx-paths extracted from the tree, and thus can greatly reduce the amount of information exchanged among processors. Our experiments show that the algorithms are capable of achieving very good speedups, and of substantially reducing the amount of time when ﬁnding frequent patterns in very large databases. ´ ´ . ’ ’ . e a a a e e T´m t˘t. B`i b´o n`y gi´.i thiˆu hai giai thuˆt song song khai th´c luˆt kˆt ho.p su. dung trˆn o a a a a o . . . ’ ’ c´c m´y t´ song song c´ bˆ nh´. phˆn t´n. C´c giai thuˆt du.o.c ph´t triˆn trˆn phu.o.ng ph´p a a ınh o o o a a a a a e e a . . . ´ ’ . ’ ınh. ’ e ınh a a y a a ` a FP-growth. Giai thuˆt th´. nhˆt thu.c hiˆn t´ to´n song song su. dung k˜ thuˆt cˆn b˘ ng tai t˜ a u . . . . . hai du.o.c ph´t triˆn du.a trˆn giai thuˆt th´. nhˆt su. dung k˜ thuˆt cˆn b˘ ng tai dˆng ’ ` ´ ’ ’ ’ o Giai thuˆt th´ a u a e e a u a ’ . y a a a . . . . . . ’ ´ ´ ´ ’ ’ e ınh a o ’ a y a a e khi mˆt cˆn b˘ ng tai xay ra. B`i b´o su. dung k˜ thuˆt ma trˆn dˆm dˆ t´ to´n trong sˆ cua c´c a a ` a a a ’ . . . . ’ ´ ’ u o ’ y y a a e o e a t´c vu v` phˆn phˆi c´c t´c vu t´.i nh˜.ng bˆ xu. l´ . K˜ thuˆt n`y giam thiˆu th`.i gian duyˆt cˆy a . a a o a a . . . . o ’ ` ’ . v` giam b´.t chi ph´ truyˆn thˆng gi˜.a c´c bˆ xu. l´ . B`i b´o c˜ ng su. dung k˜ thuˆt cˆy b˘m dˆ a ’ o e a a u y a a a ı e o u a o ’ y . . ’ ` n tˆ du.`.ng di giˆng nhau tr´ loc t`. cˆy, v` nhu. vˆy giam thiˆu lu.o.ng thˆng tin trao ´ o ´ ’ a a e o nh´m c´c tiˆ o o a e o ıch . u a . . ’ ´ ´ ´ a ´ ´ ’ ’ ’ dˆ i gi˜.a c´c bˆ xu. l´ . Kˆt qua thu. nghiˆm cho thˆ y c´c giai thuˆt dat du.o.c dˆ t˘ng tˆc rˆ t tˆt, v` o u a o ’ y e o a o a o e a a a . . . . . . ’ ´ ’ a ’ ˜ ´ ’ ım e a a o e a o giam thiˆu d´ng kˆ th`.i gian t` kiˆm c´c mˆ u phˆ biˆn trong c´c CSDL l´.n. e e o ´. ˆ 1. GIO I THIEU . B`i to´n khai th´c luˆt kˆt ho.p (Association Rule Mining - ARM) du.o.c Agrawal, Imielinski a a a a e . . . ´ .i thiˆu lˆn dˆu tiˆn. B`i to´n n`y tˆp trung t` kiˆm nh˜.ng mˆi quan hˆ c´ ´ ´ ´ e ` ` a a o e o ıch v` [1] gi´ a o e a a a a ım e u . . . ’ ˜ u e ´ . ` m ˆ n gi˜.a c´c mˆu d˜. liˆu trong mˆt CSDL. C´c luˆt kˆt ho.p d˜ v` dang du.o.c su. dung a o a a e tiˆ a e u a a a . . . . ’ . ˜ ´ ´ ´ ´ e ’ u o . e . e e rˆ t hiˆu qua trong mˆt loat c´c u.ng dung t`. hˆ tro. ra quyˆt dinh, du. b´o, y tˆ, tiˆp thi v` a o . . a . a . . . a ´ ’ quan tri kinh doanh. . . . Cho I l` mˆt tˆp c´c muc trong CSDL giao dich. Mˆt giao dich T ⊆ I du.o.c dinh ngh˜ a o a a o ıa . . . . . . . . ` ´ o o a e . u a o o l` mˆt tˆp c´c muc du.o.c sinh ra dˆ ng th`.i trong mˆt giao dich. Mˆt luˆt kˆt ho.p gi˜.a tˆp a o a a . . . . . . . . . ˜ ` ’ ’ a ’ a muc X ⊆ I v` tˆp muc Y ⊆ I , biˆ u diˆn X → Y , chı ra r˘ ng kha n˘ng hiˆn diˆn cua c´c a a e’ e a e e . . . . . ` ` ’ a phˆn tu. X trong giao dich c˜ng k´o theo kha n˘ng hiˆn diˆn cua phˆn tu. Y . Dˆ do du.o.c su. a ’ o u e e e ’ a ’ . . . . . ’ . ’ ’ ´ ´ ˆ ´ ˆ ´ ˆ ˆ PHAT TRIEN CAC GIAI THUA T SONG SONG TRONG KHAI PHA LUAT KET HO P . . . 185 ’ dung dˆ d´nh gi´ m´.c dˆ kˆt ho.p cua luˆt l` dˆ hˆ tro. (support ) v` dˆ tin cˆy (conﬁdence ). a a o o . a o e’ a a u o e . a . . . ´ . ˜ . . . cua luˆt X → Y l` ty lˆ gi˜.a sˆ giao dich ch´.a ca X v` Y v´.i tˆ ng sˆ giao dich ’ ˜ ´ ´ a a ’ e u o u ’ a o o o Dˆ hˆ tro ’ o o . . . . . . . so. d˜. liˆu. Dˆ tin cˆy cua luˆt X → Y l` ty lˆ gi˜.a sˆ giao dich ch´.a ca X v` Y ´ u ’ a o a ’ a a ’ e u o trong co ’ u e . . . . . . ` ´ u o a o a v´.i sˆ giao dich ch´.a X . Mˆt tˆp ho.p gˆ m c´c muc (item) trong CSDL goi l` mˆt tˆp muc o o . . . . . . a o a . . . .i k muc goi l` mˆt tˆp k muc (k-itemset). B`i to´n khai th´c d˜. (itemset). Mˆt tˆp muc v´ o a o a a a u . . . . . a o a . . . ´ ´ a ’ a a ´ a e . a o o u a ım e liˆu su. dung luˆt kˆt ho.p du.o.c chia th`nh hai bu.´.c. Bu.´.c th´. nhˆ t t` kiˆm tˆ t ca c´c tˆp e ’ . . ´ . . . ˜ . o ˜ . o ’ biˆn, l` tˆp muc xuˆ t hiˆn trong CSDL v´.i dˆ hˆ tro. l´.n ho.n dˆ hˆ tro. tˆi thiˆ u. ´ ´ e o o e’ muc phˆ e a a o ´ a o o o . . . . . . ’ ´ o u a a ` a a a o e Bu.´.c th´. hai du.ng c´c luˆt tiˆm ˆ n trong c´c tˆp muc phˆ biˆn. . . e ’ . . .p du.o.c du.a ra, tuy nhiˆn ch´ng dˆu g˘p ´ ` ` ’ D˜ c´ rˆ t nhiˆu giai thuˆt khai th´c luˆt kˆt ho a o a e a a a e . e a e u . . ´ . . . l´ nh˜.ng CSDL l´.n, v` viˆc t` kiˆm c´c giai ph´p ´ e . ´ ’ a ` e a ’ ’ phai vˆ n dˆ hiˆu n˘ng t´ to´n khi xu y u o a e ım e a a ınh a . ˜ ´ ´ ´ . ` ’ e a ’ e a e a e e’ e m´.i vˆn tro. nˆn cˆ p thiˆt. C´ch tiˆp cˆn song song mang lai nhiˆu triˆ n vong cho viˆc giai o a . . . ` ´ ´ e ’ ’ quyˆt vˆ n dˆ n`y. Muc tiˆu cua b`i b´o l` ph´t triˆ n c´c giai thuˆt song song nh˘ m t˘ng e a ` a e a a a a e’ a a a a . . .c hiˆn cua c´c giai thuˆt v` giam thiˆ u th`.i gian t´ to´n. ’ ’ a ’ ’ hiˆu n˘ng thu e a o a a e e ınh a . . . . ` ` o . ’ a a o a ´ u a o e a Phˆn c`n lai cua b`i b´o c´ cˆ u tr´c nhu. sau. Phˆn 2 gi´.i thiˆu phu.o.ng ph´p FP-Growth. a . . CSDL giao dich. ’ ´ ` ’ Phˆn 3 ph´t triˆ n hai giai thuˆt song song khai th´c c´c tˆp phˆ biˆn t` a a e’ a a a a o e u . . . ` ´ a a o ` n 4 tr` b`y nghiˆn c´.u hiˆu n˘ng cua giai thuˆt. Phˆn 5 tr` b`y kˆt luˆn v` hu.´.ng ’ ’ e a a a ınh a e Phˆ a ınh a e u . . . ´ nghiˆn c´.u tiˆp theo. e u e . . ´ 2. PHU O NG PHAP FP-GROWTH ´ u u e ’ . a a a Phu.o.ng ph´p FP-Growth su. dung cˆ u tr´c d˜. liˆu FP-Tree (Frequent Pattern Tree - cˆy . ’ e ’ ˜u phˆ biˆn)[5]. FP-Tree biˆ u diˆn c´c thˆng tin vˆ tˆn suˆ t cua c´c muc trong CSDL. ˜ a ` ` ´ mˆ a o ´ e e o e a a ’ a . ˜ ’ ´ ˜ ’ Mˆi nh´nh cua FP-Tree biˆ u diˆn mˆt tˆp muc phˆ biˆn, c´c n´t doc theo nh´nh du.o.c lu.u o a e’ e o a o e a u . a . . . . . theo th´. tu. giam dˆn cua tˆn suˆ t c´c muc, n´t l´ biˆ u diˆn c´c muc c´ tˆn suˆ t nho ’ ˜ a ` ´ ´ ’ ` ’ u . ’ a a a a u a e e a a tr˜ u . . o ` ’ ´ ´ ´ ´ e ` nhˆ t (muc phˆ biˆn ´ nhˆ t). FP -Tree g˘n v´.i mˆt bang tiˆu dˆ (header table). C´c muc v` a o e ıt a a o o ’ e a a . . . ` ´ ` ´ ´ ’ ’ u e ` a ’ ` a a u e u . ’ a sˆ dˆm cua ch´ng du.o.c lu.u tr˜. trong bang tiˆu dˆ theo th´. tu. giam dˆn cua tˆn suˆ t. Dˆu o e . ´ ` ´ o a ’ a u ’ ’ a mˆt muc ch´.a n´t dˆu danh s´ch liˆn kˆt v´.i tˆ t ca c´c n´t tu.o.ng u.ng cua FP-Tree. ´ a e e v`o cu a o u u a . . ` Phu.o.ng ph´p FP-Growth bao gˆ m hai nhiˆm vu ch´ a o e ınh: 1) xˆy du.ng FP-Tree, v` 2) khai th´c a a a . . . ’ e ’ . ˜u phˆ biˆn su. dung FP-Tree. ´ c´c mˆ a a o .ng FP-Tree Xˆy du a . ` ` ` ´ ´ ’ a e a a e u a ım a ’ Dˆ xˆy du.ng FP-Tree cˆn phai qu´t CSDL hai lˆn. Lˆn qu´t th´. nhˆ t t` tˆ t ca 1e’ a . ’ biˆn. Sau d´ c´c muc n`y du.o.c ch`n v`o bang tiˆu dˆ, theo th´. tu. giam dˆn ` ’ itemsets phˆ e o ´ o a a e u . ’ e a e ` a . . ’ ´ ´ ´ ` ’ ` a a ’ a o o e cua tˆn suˆ t. Lˆn qu´t th´. hai xˆy du.ng FP-Tree. Tˆ t ca c´c muc khˆng phˆ biˆn trong a a a e u . . ´ ´ ` ´ ’ a u . ’ a ’ ` a a giao dich du.o.c lu.o.c bo. C´c muc c`n lai s˘p xˆp theo th´. tu. giam dˆn cua tˆn suˆ t, sau d´ o . . . o . a e . ´ ` o o o a e a a o a e o a u e ´ du.o.c ch`n v`o FP-Tree th`nh mˆt nh´nh. Nˆu mˆt tˆp muc d`ng chung tiˆn tˆ v´.i mˆt tˆp . . . . . . . ˜ a ` ` o ’ e ´ a a e’ e . muc d˜ tˆ n tai trong cˆy, tˆp muc m´.i s˜ d`ng chung tiˆn tˆ cua nh´nh cˆy biˆ u diˆn tˆp a o . a a o e u . . . ˜ ´ ´ u o o e o e u o muc d´. Ho.n n˜.a, mˆt bˆ dˆm du.o.c g˘n v´.i mˆi n´t trˆn cˆy. Bˆ dˆm lu.u tr˜. sˆ giao dich . . ´ . a o o u e a . ´ . . o .a tˆp muc biˆ u diˆn bo.i du.`.ng dˆn t`. gˆc t´.i n´t. Bˆ dˆm n`y du.o.c cˆp nhˆt trong suˆt ˜ ˜ ´ ´ ´ ’ a ch´ a u . e’ e o a u o o u o e a a o . . . . . ` n qu´t th´. hai, khi mˆt nh´nh m´.i du.o.c ch`n thˆm. o a o e e lˆ a e u . . . dung FP-Tree ’ ´ ’ Khai th´c c´c tˆp phˆ biˆn su . a a a o e . ’ Cho muc i trong bang tiˆu dˆ cua FP-Tree Tα (α l` mˆt tˆp muc, v` Ti biˆ u thi FP-Tree e ` ’ e a o a a e’ . . . . . .o.c xˆy du.ng t`. CSDL ban dˆu), theo danh s´ch kiˆn kˆt b˘t dˆu tai muc i trong bang ´ ` ` ´ ’ du . a a e e a a . a u . . ˜ ´ ` tiˆu dˆ cua Tα , tˆ t ca c´c nh´nh ch´.a muc i du.o.c th˘m. C´c nh´nh d´ tao th`nh mˆu diˆu e ` ’ e a ’ a a u o . a a e a a a . . ˜ ˆ NGUYEN LONG GIANG 186 ’ ´ ˜ ´ ` ’ ’ kiˆn co. so. cua α ∪ i, v` vˆy h`ng ngang thu du.o.c tˆ t ca c´c muc phˆ biˆn trong mˆu diˆu e ı a a o e a e . . . a ’ a . . so. n`y. Tiˆp theo phu.o.ng ph´p FP-Growth xˆy du.ng FP-Tree diˆu kiˆn T , b˘ ng ´ ` e a a e e α∪i ` a kiˆn co ’ a e . . . ’ ´ ´ ’ . ` ` ’ a a a a o e e ` ’ o . e o viˆc kho.i tao lˆn dˆu bang tiˆu dˆ cua n´ du.a v`o c´c muc phˆ biˆn du.o.c t` thˆ y, sau d´ e . . ım a . ´ ´ ` ` ’ tiˆn h`nh th˘m c´c nh´nh cua Tα theo danh s´ch liˆn kˆt cua i mˆt ho˘c nhiˆu lˆn v` ch`n e a a a a a e e ’ o a e a a e . . c´c tˆp muc tu.o.ng u.ng v`o Tα∪i. Ch´ y r˘ ng th´. tu. cua c´c muc c´ thˆ kh´c nhau trong a a ´ a u´ ` a u . ’ a . . . o e’ a ´ ’ u ’ . ’ e e a u e o Tα v` Tα∪i. Thu tuc o. trˆn du.o.c su. dung dˆ quy, v` d`.ng lai khi FP-Tree kˆt qua ch´.a mˆt a . . ’ . . . .`.ng di do.n duy nhˆ t. Tˆp dˆy du c´c tˆp muc phˆ biˆn du.o.c sinh ra t`. tˆ t ca c´c du.`.ng ’ e ´ ´ ’ a a du o a o ´ a a ` u a ’ a o . . . . ’ di do.n cua FP-Tree. . ’ ´ ´ ´ ˆ ˆ ˆ ` 3. CAC GIAI THUAT SONG SONG, THIET KE VA THU C THI . . ´ ` ’ Phˆn chia CSDL ban dˆu v` t´ a a a ınh d´ ng d˘ n cua phu.o.ng ph´p u a a ’ ` ` ´ ` a o Nˆu N l` tˆ ng c´c bˆ xu. l´, CSDL ban dˆu du.o.c chia th`nh N phˆn b˘ ng nhau, sau d´ e a o a o ’ y a a a . . .o.c g˘n v`o c´c bˆ xu. l´ kh´c nhau, v` du.o.c lu.u tr˜. trong bˆ nh´. cuc bˆ cua ˜ ´ ` mˆi phˆn du . a a a o ’ y a o a a u o o . o ’ . . . . ˜ . ´ n´. Mˆi bˆ xu. l´ s˜ qu´t CSDL giao dich cuc bˆ mˆt lˆn v` liˆt kˆ nh˜.ng su. cˆ cuc bˆ. Sau o o o ’ y e e . . o o ` . . a a e e u . . o . o . ’ ´ a ’ ´ ´ ´ o e ` e d´ tˆ t ca c´c bˆ xu. l´ s˜ thu du.o.c c´c muc phˆ biˆn b˘ ng viˆc trao dˆ i c´c sˆ dˆm cuc bˆ o a ’ a o ’ y e o a o e . a . . . . o . .i tˆ t ca c´c bˆ xu. l´ kh´c su. dung ph´p r´t gon tˆ ng to`n cuc (global sum-reduction). C´c ’ ´ ’ a o ’ y a ’ . e u . o a . a v´ a o . ’ ´ ´ ´ ` u . ’ a muc phˆ biˆn n`y du.o.c s˘p xˆp theo th´. tu. giam dˆn theo dˆ hˆ tro. dˆ xˆy du.ng L, danh o e a o o . e’ a . a e . . . ˜ ˜ . ’ biˆn. Ch´ y r˘ ng L giˆng nhau v´.i tˆ t ca c´c bˆ xu. l´. Mˆi bˆ xu. l´ qu´t ` ´ ´ o o ’ y e s´ch c´c muc phˆ e a a o ´ u´ a o o a ’ a o ’ y . . ´ ´ ’ e’ a d˜. liˆu cuc bˆ dˆ xˆy du.ng FP-Tree cuc bˆ, giˆng nhu. giai thuˆt xˆy du.ng FP-Tree. Dˆ n˘m u e . o e’ a a a . . . . o o . . . ´ r˜ tiˆn tr` n`y, x´t v´ du sau. o e ınh a e ı . ´ ’ V´ du 1. Cho CSDL giao dich, DB , l` hai cˆt dˆu tiˆn trong Bang 1, sˆ lu.o.ng bˆ xu. l´ l` 3 ı . a o ` o ’ y a o . . . a e . .˜.ng hˆ tro. tˆi thiˆ u l` 5. V´ du n`y minh hoa qu´ tr` xˆy du.ng FP-Tree cuc bˆ. ˜ ´ o . o e’ a ı . a a ınh a v` ngu o a . . . o . ’ Bang 1. V´ du vˆ viˆc phˆn chia CSDL giao dich ı . ` e e . a . ID 1 2 3 4 5 6 7 8 9 C´c muc trong giao dich a . . A, B, C, D, E F, B, D, E, G B, D, A, E, G A, B, F, G, D B, F, D, G, K A, B, F, G, D A, R, M, K, O B, F, G, A, D A, B, F, M, O ’ ´ C´c muc du.o.c phˆ biˆn a o e . . BAD BDFG BADG BADFG BDFG BADFG A BADFG BAF Bˆ xu. l´ o ’ y . P0 P1 P2 ˜ . ´ a a o o ’ y o o ’ y e CSDL du.o.c phˆn t´n nhu. nhau t´.i 3 bˆ xu. l´. Mˆi bˆ xu. l´ dˆm dˆ hˆ tro. cua c´c muc o o . ’ a . . . . ˜ . liˆu cuc bˆ. Sau ph´p r´t gon tˆ ng to`n cuc, tˆ t ca c´c bˆ xu. l´ lˆ y sˆ ’ ´ ’ a o ’ y a o ´ ´ o e u . o a a c´ m˘t trong d˜ e o a u . . . . . . ` ´ ´ ´ ´ ´ a e a o e dˆm to`n cuc dˆi v´.i tˆ t ca c´c muc trong CSDL. B˘ ng viˆc so s´nh sˆ dˆm dˆ hˆ tro. v´.i e a o o . o . . . o o a ’ a . ˜ ’ ˜ o ’ y a ’ e ˜ tro. tˆi thiˆ u, mˆi bˆ xu. l´ lˆ y danh s´ch L, danh s´ch c´c muc phˆ biˆn{(B:8), (A:7), ´ ´ ´ e o . a a a o dˆ hˆ . o o o . . ’ ´ ˜ ´ ´ a e u . ’ (D:7), (F:6), (G:6)}. C´c muc phˆ biˆn trong mˆi giao dich du.o.c s˘p xˆp theo th´. tu. cua L a o e o . . . . ba cua Bang 1). Mˆi bˆ xu. l´ xˆy du.ng FP-Tree cuc bˆ mˆt c´ch dˆc lˆp. Tˆ t ca ˜ o ’ y a ´ ’ ’ (cˆt th´ o u o a a ’ o . . . . . . o o a . . FP-Tree cuc bˆ du.o.c minh hoa trong H` 1. o ınh . . . . . ’ ’ ´ ´ ˆ ´ ˆ ´ ˆ ˆ PHAT TRIEN CAC GIAI THUA T SONG SONG TRONG KHAI PHA LUAT KET HO P . . . 187 H` 1. C´c FP-Tree cuc bˆ ınh a . o . ´ ’ a o Viˆc xˆy du.ng FP-Tree cuc bˆ khˆng phai l` bu.´.c cuˆi c`ng nhu.ng c´ y ngh˜ kh´m ph´ e a o u o´ ıa a a . . . o o . ’ ´ ˜ ´ ` ’ a tˆ t ca c´c mˆu phˆ biˆn m` khˆng phai qu´t thˆm CSDL lˆn n`o n˜.a. Theo phu.o.ng ph´p a ’ a a o e a o e e a a u ’ ´ ˜ ´ ´ ’ e’ a a ’ a a o e e e o e FP-growth, dˆ khai th´c tˆ t ca c´c mˆu phˆ biˆn liˆn quan dˆn mˆt muc i (trong bang tiˆu . . .ng mˆu diˆu kiˆn co. so. cua i v` sau d´ xˆy du.ng FP-Tree diˆu kiˆn cua i l` ˜ ` ` ` ` ’ ’ dˆ), cˆn xˆy du e a a e e o a e e ’ a a a . . . . .ng nh´nh ch´.a muc i thu.`.ng hiˆn diˆn trong nhiˆu FP-Tree cuc bˆ v` cˆn thu thˆp ` Ti . Nh˜ u a u o e e e a a . . . . o a ` . . ´ ` ` ’ ’ ’ ’ o e e e e ch´ng t`. tˆ t ca c´c bˆ xu. l´ dˆ xˆy du.ng diˆu kiˆn co. so. cua i. Diˆu kiˆn co. so. cua mˆt u u a ’ a o ’ y e’ a . . . . . .o.c ’ ` ` muc thay dˆ i theo c´ch phˆn chia CSDL ban dˆu. Tuy nhiˆn, FP-Tree diˆu kiˆn m` du . o a a a e e e a . . ’ ’ ´ ` ’ o o e a u a xˆy du.ng trˆn diˆu kiˆn co. so. d´ khˆng thay dˆ i v` c´c tˆp phˆ biˆn du.o.c khai th´c t`. cˆy a e e o a a a o e . . . . .o.ng. Dˆ ch´.ng minh t´ ch´ x´c cua c´ch tiˆp cˆn n`y, x´t hai bˆ ’ ´ . c˜ng khˆng bi anh hu ’ u o e’ u ınh ınh a ’ a e a a e o . ’ ` sau. dˆ e ’ e ` ´ ` ’ ’ Bˆ dˆ 1. C´ch phˆn chia CSDL ban dˆu khˆng anh hu.o.ng dˆn FP-Tree diˆu kiˆn cua mˆt o ` a a a o ’ e e e o . . muc. . ˜ ´ a e ınh a o a Ch´.ng minh. Du.a v`o tiˆn tr` xˆy du.ng FP-Tree, mˆi giao dich trong CSDL ´nh xa t´.i u . . . . o .`.ng di trong FP-Tree. Mˆt du.`.ng di do.n i → i → · · · → i trong du.`.ng di c´ tiˆn o o o o ` e mˆt du o o 1 2 n . . .n nhˆ t theo mˆu i1 → i2 → · · · → ik ’ ´ ˜ ´ ´ ´ a y a ’ a o a o e o tˆ i1 d˘ng k´ tˆ t ca c´c giao dich c´ tˆp phˆ biˆn l´ o a a . . ´ ´ ` ’ a e a a o e v´.i 1 k n. Khi xˆy du.ng FP-Tree diˆu kiˆn, mˆt c´ch do.n gian l` thˆm c´c sˆ dˆm v`o o e e o a a . . . .`.ng di i1 → i2 → · · · → in . V` thˆ su. phˆn t´n c´c giao dich khˆng anh hu.o.ng t´.i du.`.ng ´ ’ a a a o ’ o o du o ı e . . ´ ´ ´ ` ’ o ´ ’ a o di i1 → i2 → · · · → in v` sˆ dˆm cua n´. Ap dung diˆu n`y t´.i tˆ t ca c´c du.`.ng di cua cˆy a o e e a o a ’ a . ’ e ` diˆu kiˆn ta c´ bˆ dˆ. e e o o ` . ’ ´ a ’ ’ e ˜ a o e ` Bˆ dˆ 2. Khai th´c FP-Tree cuc bˆ thu du.o.c c´c mˆu phˆ biˆn dˆy du. o ` a . a . o . ` ´ ’ u ´ a a e ` ’ a ’ a o ’ y a Ch´.ng minh. Ch´ y r˘ ng c´c muc trong bang tiˆu dˆ cua tˆ t ca c´c bˆ xu. l´ l` nhu. nhau u e . . ˜ ’ o a o ’ y ` ´t kˆ sˆ c´c bˆ xu. l´ N v` c´ch phˆn t´n giao dich. C˜ng ch´ y r˘ ng ph´p xu. l´ mˆi muc ´ ’ y o a a a a u u´ a e bˆ e a . . . . so. cua n´) du.o.c ˜ ˜ ` ’ e ıa a o a a e e trong bang tiˆu dˆ l` t´c vu dˆc lˆp. Ngh˜ l` mˆi muc (v` mˆu diˆu kiˆn co ’ ’ o e ` a a . o a . . . . . ’ ´ ˜ ´ ` ’ y o a e’ ’ a ’ a a o e o e a o a e o xu. l´ dˆc lˆp dˆ san sinh tˆ t ca c´c mˆu phˆ biˆn c´ liˆn quan m` khˆng cˆn thˆm thˆng . . ’ e ` ´ e ´ ´ e e ’ o o a tin n`o n˜.a. Cuˆi c`ng, theo Bˆ dˆ 1, FP-tree diˆu kiˆn cua mˆt muc l` bˆ t biˆn, n´i c´ch a u o u o ` . . . a a ’ ’ e ˜u phˆ biˆn du.o.c san sinh t`. FP-tree diˆu kiˆn d´ khˆng thay dˆ i. V` vˆy ta c´ ` e e o o o ı a o kh´c, c´c mˆ a a a o ´ u . . . ’ ’ e bˆ dˆ. o ` ’ e ˜ ´ ´ . ` Bˆ dˆ 2 cho thˆ y t´ ch´ x´c cua c´ch tiˆp cˆn. Do viˆc t´ to´n tai mˆi phˆn tu. o ` a ınh ınh a ’ a e a e ınh a . o a ’ . 188 ˜ ˆ NGUYEN LONG GIANG ´ ’ trong bang tiˆu dˆ l` t´c vu dˆc lˆp nˆn ta c´ thˆ khai th´c song song tˆ t ca c´c FP-Tree e ` a a . o a e e o e’ a a ’ a . . . l´. Tuy nhiˆn, tai trong cˆng viˆc ´ ’ e o e a o ’ cuc bˆ b˘ ng c´ch phˆn phˆi c´c t´c vu d´ cho c´c bˆ xu y a a o a a . o . . . . o ` . a .`.ng khˆng b˘ ng nhau, diˆu d´ dˆn t´.i su. mˆ t cˆn b˘ ng tai trong cˆng ` ˜ o . a a ` ´ ` ’ ’ a a . o o a a o e o a cua c´c t´c vu d´ thu o . ’ a e viˆc, v` v` vˆy giam thiˆ u hiˆu n˘ng t´ to´n. Muc tiˆu b`i b´o l` t` ra phu.o.ng ph´p hiˆu e a ı a e’ e a ınh a e a a a ım . . . . . ’ phˆn phˆi c´c t´c vu d´ dˆu nhau cho c´c bˆ xu. l´ v` giam thiˆ u su. mˆ t cˆn b˘ ng ’ . a a ` ´ ´ ’ e o a a . o ` e a o ’ y a ’ qua dˆ a e a . ’ tai trong cˆng viˆc. o e . . ` ´ ’ ınh ( SLB Static y a a a Thuˆt to´n phˆn phˆi t´c vu su. dung k˜ thuˆt cˆn b˘ ng tai t˜ a a a o a . . . ’ . Load Balancing) ´ ´ ´ ’ ’ Y tu.o.ng thuˆt to´n l` x´c dinh khˆi lu.o.ng t´ to´n cho tˆ t ca c´c muc trong bang tiˆu a a a a . ınh a a ’ a e o . . . .o.c xˆy du.ng t`. co. so. d˜. liˆu ban dˆu) v` sau d´ chia nh˜.ng ` ’ ` ` ’ u e u dˆ cua FP-Tree ban dˆu (cˆy du . a e a a a a o u . . ` ` n c´ k´ thu.´.c b˘ ng nhau v` g´n ch´ng cho c´c bˆ xu. l´. ’ y o a a a u a o a a muc d´ th`nh c´c phˆ o ıch . . o a ’ y ` ’ Cho T = {t1 , t2 , . . ., tn } l` tˆp t´c vu, v´.i t´c vu ti dang xu. l´ phˆn tu. i trong bang tiˆu a a a . o a . a ’ e . . so. cua n´ dˆ san sinh tˆ t ca c´c mˆu phˆ biˆn liˆn quan, v´.i n l` sˆ t´c ’ ’ ’ e e ˜ ` a ` ´ ´ dˆ, v` diˆu kiˆn co ’ ’ o e e e e a ’ a a o ´ o a o a . vu. . ´ ´ a o o e Cho W = {w1, w2, . . . , wn} l` tˆp trong sˆ v´.i wi = weight(ti) l` khˆi lu.o.ng cˆng viˆc a a o o . . . . ’ xu. l´ t´c vu ti cho dˆn khi kˆt th´c. Trong sˆ n`y c´ thˆ l` mˆt dˆ do th`.i gian t´ to´n ’ a o o ´ ´ u ´ ınh a dˆ ’ y a . e e e o a o e o . . . ˜ ´ a o o a e’ e o o o e o thu.c, ho˘c dˆ do biˆ u diˆn mˆt th`.i gian tu.o.ng dˆi, liˆn quan t´.i th`.i gian du.o.c yˆu cˆu . . . e ` . . ’ xu. l´ c´c t´c vu kh´c. Trong tru.`.ng ho.p n`y, viˆc u.´.c lu.o.ng th`.i gian t´ to´n thu.c l` dˆ ’ y a a . e a o a e o o ınh a . . . . a ´ ´ . o o khˆng thˆ . Ta s˜ theo c´ch tiˆp cˆn u.´.c lu.o.ng th`.i gian tu.o.ng dˆi. o e’ e a e a o . ` ´ ’ o e a a ` a ’ Dˆ xu. l´ phˆn tu. i , tru.´.c hˆt xˆy du.ng cˆy diˆu kiˆn cua i, b˘ ng c´ch dˆ quy san sinh ra e’ ’ y ` e e ’ a a e . . . ˜u diˆu kiˆn co. so. v` FP-Tree kˆ tiˆp cho dˆn khi tˆ t ca FP-Tree tro. th`nh du.`.ng di ´ e ´ ` ´ ´ ’ ’ a ’ a o e e e e a c´c mˆ a a . ´ o a o a ´ ` ` o o u o e do.n. Sˆ bu.´.c l˘p c˜. h`m sˆ m˜ v´.i chiˆu cao FP-Tree diˆu kiˆn cua i. R˜ r`ng l` chiˆu cao e e ’ o a a ` e . . .`.ng d`i nhˆ t gi´.i han bo.i sˆ tˆi da c´c muc phˆ biˆn trong ’ e ´ ´ ´ ’ o o ’ a a o . a o ´ cua FP-Tree l` chiˆu d`i cua du o a ` e a ’ . ´ ´ ´ ’ e o . o bˆ t k` giao dich n`o thuˆc CSDL, ho˘c sˆ muc trong bang tiˆu dˆ cua n´. Do d´, trong sˆ a y a o a o . e ` ’ o . . . ’ u.´.c lu.o.ng b˘ ng cˆng th´.c sau ` ’ a . cua t´c vu ti c´ thˆ o o e a o u . ´ ’ wi = f (sˆ muc trong bang tiˆu dˆ). o . e ` e .c hiˆn, ta su. dung cˆng th´.c ’ . e o u Dˆ thu e’ . . ´ ’ e wi = sˆ muc trong bang tiˆu dˆ o . e ` n .i c´c bˆ xu. l´ su. dung giai thuˆt d´ng g´i nhi ’ y ’ . ’ o Cho W = i=1 wi . Ta phˆn t´n t´c vu t´ a o a a a . o a o . . . . l´, trong sˆ cua mˆi khˆi l` W , ˜ . ˜ ´ ´ ´ ´ phˆn (bin-packing). Cˆ p ph´t mˆt ”khˆi” cho mˆi bˆ xu y . a a a o o o o ’ o ’ o o a N . ´ v´.i N l` sˆ lu.o.ng bˆ xu. l´. Dˆ t˘ng hiˆu n˘ng song song, phˆn t´n dˆu c´c t´c vu c`ng trong o a o . o ’ y e’ a e a a a ` a a . u e . . . .i c`ng nhiˆu khˆi c`ng tˆt, tr´nh tru.`.ng ho.p c´c t´c vu v´.i trong sˆ l´.n du.o.c phˆn t´n ` ´ ´ ´ ´ e o a o a o a a . o o o a a sˆ t´ a o o . . . ´ ´ ´ ` ` o a o e u . ’ a ’ e’ . e a a a . t´.i mˆt v`i khˆi. Dˆ thu.c hiˆn diˆu n`y, c´c t´c vu du.o.c s˘p xˆp theo th´. tu. giam dˆn cua o . . . a e . tu. s˘p xˆp t´.i khˆi b´ nhˆ t. Tiˆn tr` n`y du.o.c thu.c ˜ ´ ´ ´ ´ ´ ´ o e a e ınh a trong sˆ, v` g´n mˆi t´c vu theo th´ . a e o o a a o a . u . . . ` ´ o e a ’ a o ’ y hiˆn dˆ ng th`.i trˆn tˆ t ca c´c bˆ xu. l´. e o . . ´ ´ Du.´.i dˆy tr` b`y viˆc su. dung k˜ thuˆt ma trˆn dˆm dˆ d´nh gi´ trong sˆ t´c vu. ınh a e ’ . e’ a a . o a . o a y a a e . . . ´ K˜ thuˆt Ma trˆn Dˆm y a a e . . ˜ ’ a o o e ` ’ e Trong phu.o.ng ph´p FP-growth, v´.i mˆi muc i trong bang tiˆu dˆ cua FP-Tree Ti, hai . .`.ng ngang cua T du.o.c su. dung dˆ xˆy du.ng FP-Tree diˆu kiˆn T . Du.`.ng ngang th´. nhˆ t ’ a ´ ` ’ i o u a du o e e e i . ’ . . . .ng bang tiˆu dˆ cua cˆy m´.i b˘ ng viˆc t` tˆ t ca c´c muc phˆ biˆn trong mˆu diˆu ’ ´ ˜ ´ ` ’ e ` ’ a a e ım a ’ a o e a e o ` e xˆy du a . . . . so. cua i. Du.`.ng ngang th´. hai xˆy du.ng cˆy m´.i T . Trong mˆi tru.`.ng song song, kiˆn co ’ ’ e o u a a o i o o . . ´ e’ ınh a o a . sau khi duyˆt cˆy, tˆ t ca c´c bˆ xu. l´ cˆn liˆn lac v´.i nhau dˆ h` th`nh thˆng tin to`n cuc. e a a ’ a o ’ y ` e . o a . .