Tóm tắt: Khai phá đồ thị là một nhiệm vụ quan trọng của khai phá dữ liệu đồ thị
và nó có rất nhiều ứng dụng trong thực tiễn, ví dụ như: phân tích liên kết web, phân
tích mạng xã hội, phát hiện gian lận, phát hiện ngoại lệ, phân tích phân tử hóa
học,. Tuy nhiên, khai phá đồ thị con phổ biến có một hạn chế nghiêm trọng khi áp
dụng vào thực tế, đó là khó xác định được giá trị ngưỡng minSup phù hợp. Nếu đặt
minSup quá cao thì chỉ một ít đồ thị con phổ biến được tìm thấy và như vậy thông
tin hữu ích có thể bị bỏ lỡ. Nhưng nếu đặt minSup quá thấp, thời gian khai phá có
thể rất lâu và một số lượng rất lớn các đồ thị con phổ biến có thể được tìm thấy. Do
đó, việc xác định một giá trị minSup phù hợp để tìm các đồ thị con phổ biến vừa đủ
có thể rất tốn thời gian. Thuật toán khai phá Top-K đồ thị con phổ biến đã được đề
xuất đề giải quyết hạn chế này. Một số thuật toán khai phá Top-K đồ thị con phổ
biến đã được đề xuất; tuy nhiên, hầu hết đều là các thuật toán tuần tự không thể mở
rộng trên các bộ dữ liệu lớn.
Trong bài báo này, chúng tôi đề xuất một thuật toán song song để khắc phục
điểm yếu này. Hiệu suất và khả năng mở rộng của thuật toán đề xuất được minh
họa thông qua các thực nghiệm trên hai bộ dữ liệu cụ thể.
10 trang |
Chia sẻ: thanhle95 | Lượt xem: 625 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Thuật toán song song khai phá Top-K đồ thị con phổ biến, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Hội thảo Quốc gia FEE, 10 - 2020 437
THUẬT TOÁN SONG SONG KHAI PHÁ TOP-K
ĐỒ THỊ CON PHỔ BIẾN
Phạm Văn Lai1*, Nguyễn Mạnh Hùng2, Nguyễn Doãn Cường1, Phan Việt Anh2
Tóm tắt: Khai phá đồ thị là một nhiệm vụ quan trọng của khai phá dữ liệu đồ thị
và nó có rất nhiều ứng dụng trong thực tiễn, ví dụ như: phân tích liên kết web, phân
tích mạng xã hội, phát hiện gian lận, phát hiện ngoại lệ, phân tích phân tử hóa
học,... Tuy nhiên, khai phá đồ thị con phổ biến có một hạn chế nghiêm trọng khi áp
dụng vào thực tế, đó là khó xác định được giá trị ngưỡng minSup phù hợp. Nếu đặt
minSup quá cao thì chỉ một ít đồ thị con phổ biến được tìm thấy và như vậy thông
tin hữu ích có thể bị bỏ lỡ. Nhưng nếu đặt minSup quá thấp, thời gian khai phá có
thể rất lâu và một số lượng rất lớn các đồ thị con phổ biến có thể được tìm thấy. Do
đó, việc xác định một giá trị minSup phù hợp để tìm các đồ thị con phổ biến vừa đủ
có thể rất tốn thời gian. Thuật toán khai phá Top-K đồ thị con phổ biến đã được đề
xuất đề giải quyết hạn chế này. Một số thuật toán khai phá Top-K đồ thị con phổ
biến đã được đề xuất; tuy nhiên, hầu hết đều là các thuật toán tuần tự không thể mở
rộng trên các bộ dữ liệu lớn.
Trong bài báo này, chúng tôi đề xuất một thuật toán song song để khắc phục
điểm yếu này. Hiệu suất và khả năng mở rộng của thuật toán đề xuất được minh
họa thông qua các thực nghiệm trên hai bộ dữ liệu cụ thể.
Từ khóa: Khai phá đồ thị; Khai phá đồ thị con phổ biến; Khai phá Top-K đồ thị con phổ biến.
1. ĐẶT VẤN ĐỀ
Khai phá đồ thị con phổ biến là một chủ đề quan trọng trong lĩnh vực khai phá đồ thị.
Bài toán này có nhiều ứng dụng trong thực tiễn như: phân tích liên kết web [1], phân tích
mạng xã hội [4], phát hiện ngoại lệ [2], phân tích phân tử hoá học [3],... Mục tiêu của khai
phá đồ thị con phổ biến (FSM) là tìm ra tất cả các đồ thị con có tần suất xuất hiện lớn hơn
hoặc bằng giá trị ngưỡng minSup do người dùng chỉ định.
Tuy nhiên, hạn chế của các thuật toán khai phá đồ thị con phổ biến là người dùng
thường khó chọn được một giá trị minSup phù hợp. Nếu ngưỡng minSup quá cao, chỉ một
vài đồ thị con phổ biến được tìm thấy và như vậy, người dùng có thể bỏ lỡ thông tin có giá
trị. Mặt khác, nếu ngưỡng quá thấp, một lượng rất lớn đồ thị con phổ biến được tìm thấy
đồng thời yêu cầu thời gian tính toán cao và tốn bộ nhớ. Vì người dùng thường chỉ quan
tâm một lượng thông tin nhất định để phân tích, nên họ thường quan tâm đến việc tìm đủ
một số đồ thị con phổ biến nào đó. Việc xác định một giá trị minSup phù hợp để tìm ra đủ
số lượng các đồ thị con phổ biến rất khó vì nó phụ thuộc vào từng bộ dữ liệu mà người
dùng thường không biết. Do đó, người dùng phải tốn rất nhiều thời gian để chạy thuật toán
nhiều lần với các giá trị minSup khác nhau đến khi đạt được kết quả mong muốn.
Để giải quyết vấn đề này, Li et al. [6] đã đề xuất thuật toán TGP để tìm trực tiếp k đồ
thị con đóng phổ biến nhất trong cơ sở dữ liệu đồ thị, trong đó giá trị k do người dùng
chọn. Cách tiếp cận này có ưu điểm là trực quan cho người dùng vì người ta có thể chỉ
định trực tiếp số lượng đồ thị con phổ biến cần tìm. Tuy nhiên, một vấn đề lớn là TGP tạo
ra tất cả các đồ thị con phổ biến và sau đó tìm ra k đồ thị con đóng phổ biến nhất. Việc số
lượng đồ thị con phổ biến có thể tăng theo cấp số nhân theo kích thước của đồ thị, dẫn đến
cách tiếp cận này không hiệu quả.
Để giải quyết các nhược điểm trên, thuật toán TKG[7] đã được đề xuất để khai phá ra
chính xác k đồ thị con phổ biến.
Đã có một số thuật toán khai phá Top-K đồ thị con phổ biến được đề xuất. Tuy nhiên,
Toán học – Công nghệ thông tin
P. V. Lai, , P. V. Anh, “Thuật toán song song khai phá Top-K đồ thị con phổ biến.” 438
đều là các thuật toán tuần tự, do đó, mất nhiều thời gian tính toán để khai phá các bộ dữ
liệu lớn. Cùng với sự phát triển của phần cứng hiện đại, bộ xử lý đa nhân trở thành xu
hướng chủ đạo khi Intel và AMD đều đã giới thiệu các chip đa nhân thương mại của họ
vào năm 2008 [8], cho phép tính toán song song thuận tiện, dễ dàng hơn. Do đó, bài báo
nhằm mục đích đề xuất một thuật toán song song khai phá Top-K đồ thị con phổ biến trên
kiến trúc tính toán đa nhân.
Phần còn lại của bài báo như sau: Phần 2 trình bày các nghiên cứu liên quan; Phần 3
trình bày thuật toán TKG làm cơ sở cho thuật toán đề xuất; Phần 4 đề xuất thuật toán song
song khai phá k đồ thị con phổ biến ParaTKG; Phần 5 trình bày các thực nghiệm nhằm
minh chứng hiệu suất của thuật toán đề xuất; Kết luận được trình bày trong phần 6.
2. CÁC NGHIÊN CỨU LIÊN QUAN
Khai phá đồ thị con phổ biến là một nhiệm vụ quan trọng trong khai phá dữ liệu đồ thị,
mục đích của việc khai phá đồ thị con phổ biến là để tìm ra tất cả đồ thị con có số lần xuất
hiện ít nhất là bằng với giá trị ngưỡng tối thiểu do người dùng quy định. Hầu hết các thuật
toán FSM bao gồm hai giai đoạn quan trọng: tạo các tập ứng viên và xác định tần suất xuất
hiện. Để tính tần suất xuất hiện của một đồ thị con, cần phải xác định số đồ thị trong
CSDL có đồ thị con đẳng cấu với đồ thị con này. Bài toán tìm đồ thị con và bài toán duyệt
các tập ứng viên là 02 bài toán nền tảng của các thuật toán khai phá đồ thị con phổ biến vì
đều có độ phức tạp là NP-khó [9].
Các thuật toán khai phá đồ thị con phổ biến có 02 hướng tiếp cận để sinh tập ứng viên:
phương pháp Apriori [11- 13] và phương pháp tăng trưởng mẫu [10, 11, 14, 15]. Để xác
định đồ thị con đẳng cấu các thuật toán thường sử dụng canonical adjacency matrix
(CAM) [11] and min DFS code [14].
Các thuật toán dựa trên Apriori [11-13] nói chung bao gồm hai bước: tạo ứng viên và
kiểm tra đẳng cấu. Các thuật toán dựa trên Apriori là một phần mở rộng của thuật toán
Apriori [16]. Trong khi thuật toán Apriori làm việc với các tập phần tử, các thuật toán
FSM làm việc với các đồ thị.
Trong bước đầu tiên, các ứng cử viên kích thước k được tạo ra từ các đồ thị con phổ
biến kích thước k-1 và kiểm tra xem chúng có phổ biến hay không. Các thuật toán dựa trên
Apriori thường sử dụng tính chất đóng đề giảm số lượng tập ứng viên, thu hẹp không gian
tìm kiếm. Tính chất này cụ thể là: nếu một đồ thị con không phổ biến thì tất cả các đồ thị
chứa nó cũng sẽ không phổ biến.Vì vậy, có thể cắt tỉa các tập ứng viên chứa đồ thị con
này, điều này giúp thu hẹp không gian tìm kiếm đặc biệt trong trường hợp có các đồ thị
con phổ biến kích thước lớn.
Cách tiếp cận thứ hai là thực hiện tăng trưởng mẫu và cách tiếp cận này chính là phần
mở rộng của thuật toán tăng trưởng FP [17]. Mục đích của các thuật toán dựa trên tăng
trưởng mẫu [10, 11, 14, 15] là tìm tất cả các mẫu phổ biến mà không sinh ứng cử viên.
Cách tiếp cận này dựa trên phương pháp chia để trị. Thay vì tạo ra tất cả các đồ thị con
ứng cử viên, một cạnh mới được thêm vào mọi vị trí có thể của đồ thị con phổ biến hiện
thời. Tuy nhiên, cách tiếp cận này có một nhược điểm là cùng một đồ thị con có thể được
tạo ra nhiều lần trong khi thêm vào một cạnh mới. Vấn đề này được khắc phục bằng chiến
lược mở rộng bên phải cùng (rightmost path) [10, 14].
Với mỗi ứng cử viên, thuật toán AGM [12] sẽ duyệt lại toàn bộ dữ liệu để xác định tần
suất xuất hiện. Thuật toán FSG [13] sử dụng nhãn chính tắc để tạo xác định đồ thị con
đẳng cấu. Để tạo nhãn chính tắc của đồ thị, thuật toán này sử dụng một số phương pháp
heuristic. Tuy nhiên, các phương pháp heuristic này yêu cầu một số lượng lớn các nhãn
cạnh khác nhau để xác định duy nhất một đồ thị bằng nhãn chính tắc. Thuật toán FSG vượt
trội hơn thuật toán AGM về thời gian tính toán [13].
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Hội thảo Quốc gia FEE, 10 - 2020 439
Thuật toán gSpan [14] xây dựng cây mã DFS thay thế việc sinh các tập ứng viên và sử
dụng mã DFS tối thiểu để xác định đồ thị con đẳng cấu. Vì thế, thuật toán gSpan yêu cầu sử
dụng ít bộ nhớ hơn so với FSG và vượt trội hơn FSG [14]. Thuật toán FFSM đề xuất hai
phương thức mới để tạo ứng viên: FFSMjoin và FFSM-extension và sử dụng CAM để xác
định đồ thị con đẳng cấu. FFSM chỉ nhanh hơn thuật toán gSpan trên tập dữ liệu IC93 [11].
Thuật toán MOFA [15] tạo ra nhiều bản sao. Vì thế, các đồ thị con phổ biến được tạo ra
có thể không thực sự phổ biến. Thuật toán gSpan và FFSM vượt trội hơn thuật toán
MOFA về thời gian tính toán[18].
Mặc dù đã có nhiều thuật toán được đề xuất nhưng các thuật toán khai phá đồ thị con
phổ biến có một hạn chế nghiêm trọng, đó là người dùng thường khó chọn được một giá trị
minSup phù hợp. Để giải quyết vấn đề này, bài toán khai phá Top-K đồ thị con phổ biến
đã được đề xuất. Một số thuật toán điển hình khai phá Top-K đồ thị con phổ biến là: thuật
toán TGP[6] và thuật toán TKG[7] - đây đều là các thuật toán tuần tự, do đó, đòi hỏi thời
gian lớn để khai phá các bộ dữ liệu lớn.
Với sự phát triển mạnh mẽ của phần cứng, các bộ xử lý (CPU) đa nhân, GPU và mô
hình Map/Reduce đã trở thành những nền tảng cho tính toán song song [20]. Một số thuật
toán song song đã được phát triển để giải quyết bài toán khai phá đồ thị con phổ biến. Năm
2014, Lin và các đồng nghiệp đã phát triển thuật toán song song khai phá đồ thị con phổ
biến dựa trên mô hình Map/Reduce [23], Kessl và các đồng nghiệp [22] đã đề xuất thuật
toán khai phá các mẫu cấu trúc con dựa trên đồ thị dựa trên nền tảng GPU và đã có khá
nhiều các thuật toán song song khai phá đồ thị con phổ biến dựa trên kiến trúc song song
sử dụng mô hình bộ nhớ chia sẻ được đề xuất [21, 24].
Vì là bài toán mới cho nên hiện nay chưa có nghiên cứu nào về song song hoá thuật
toán khai phá Top-K đồ thị con phổ biến. Phần tiếp theo, bài báo sẽ trình bày chi tiết thuật
toán TKG và đề xuất một thuật toán song song khai phá Top-K đồ thị con phổ biến trên
kiến trúc tính toán đa nhân.
3. THUẬT TOÁN TKG
Trong phần này, bài báo trình bày tóm tắt thuật toán TKG (Top-K Graph miner) vì nó
là thuật toán cơ sở để chúng tôi đề xuất thuật toán song song ParaTKG.
Định nghĩa 1 (Đồ thị có gán nhãn). Một đồ thị có gán nhãn G là một bộ năm thành
phần G = (V, E, LV, LE, φV và φE). Trong đó: V, E, LV và LE lần lượt là các tập cạnh, tập
đỉnh, tập nhãn đỉnh và tập nhãn cạnh; φV và φE lần lượt là các hàm ánh xạ các đỉnh và cạnh
tới nhãn của chúng (φV: V→ LV và φE: E→ LE).
Định nghĩa 2 (Cơ sở dữ liệu đồ thị). Một cơ sở dữ liệu đồ thị GD = {G1, G2, ..., Gn}
được định nghĩa là một tập hợp n đồ thị có gán nhãn.
Định nghĩa 3 (Đồ thị đẳng cấu). Cho đồ thị có gán nhãn Gx = (Vx, Ex, LxV, LxE, φxV,
φxE) và một đồ thị có gán nhãn khác Gy = (Vy, Ey, LyV, LyE, φyV, φyE). Người ta nói rằng, đồ
thị Gx là đẳng cấu với Gy nếu tồn tại một ánh xạ f: Vx→Vy thoả mãn hai điều kiện sau:
Điều kiện 1: Đối với bất kỳ đỉnh v∈Vx thì LxV(v) = LyV (f(v)).
Điều kiện 2: Đối với cặp đỉnh (u, v)∈Ex bất kỳ thì (f (u), f (v)) ∈ Ey và LxE (u, v) = LyE
(f (u), f (v)).
Để kiểm tra xem một đồ thị con có xuất hiện trong một đồ thị hay không, mối quan hệ
đồ thị con đẳng cấu và khái niệm hỗ trợ được định nghĩa như sau.
Định nghĩa 4 (Đồ thị con đẳng cấu). Cho hai đồ thị Gx = (Vx, Ex, LxV, LxE, φxV, φxE) và
Gz = (Vz, Ez, LzV, LzE, φzV, φzE). Đồ thị Gx được xác định là xuất hiện trong đồ thị Gz, hoặc
Gx là một đồ thị con đẳng cấu của Gz, nếu Gx là đẳng cấu với một đồ thị con Gy ⊆ Gz.
Toán học – Công nghệ thông tin
P. V. Lai, , P. V. Anh, “Thuật toán song song khai phá Top-K đồ thị con phổ biến.” 440
Mục tiêu của khai phá đồ thị con phổ biến là tìm ra tất cả các đồ thị con có độ hỗ trợ
lớn hơn hoặc bằng minSup. Độ hỗ trợ được định nghĩa dựa trên khái niệm đồ thị đẳng cấu
và đồ thị con đẳng cấu.
Định nghĩa 5. Cho một cơ sở dữ liệu đồ thị GD. Độ hỗ trợ (tần suất xuất hiện) của một đồ
thị con Gx trong GD được định nghĩa là sup(Gx) = |{g|g∈GD và Gx đẳng cấu với đồ thị g}|.
Định nghĩa 6 (Khai phá đồ thị con phổ biến). Cho một giá trị ngưỡng minSup>0 do
người dùng xác định và một cơ sở dữ liệu đồ thị GD. Bài toán khai phá đồ thị con phổ biến
tìm tất cả các đồ thị con có độ hỗ trợ không nhỏ hơn minSup.
Định nghĩa 7 (Khai phá Top-k đồ thị con phổ biến). Cho một giá trị tham số k ≥ 1
được người dùng xác định và một cơ sở dữ liệu đồ thị GD. Bài toán khai phá Top-k đồ thị
con phổ biến là đi tìm một tập T gồm k đồ thị con sao cho độ hỗ trợ của chúng lớn hơn
hoặc bằng với bất kỳ đồ thị con nào khác không có trong T.
Định nghĩa 8 (Mở rộng đường dẫn bên phải cùng). Thực hiện tìm kiếm theo chiều
sâu trên đồ thị bằng việc sử dụng một ngăn xếp. Các đỉnh trong ngăn xếp tạo thành đường
dẫn bên phải cùng trong đồ thị và đỉnh hiện thời đang được xử lý được gọi là đỉnh bên
phải cùng. Việc mở rộng đường dẫn bên phải cùng thực hiện hai loại mở rộng: mở rộng
tiến (forward extensions) và mở rộng lùi (backword extensions). Mở rộng lùi được thực
hiện trước mở rộng tiến. Đối với mở rộng tiến, đỉnh bên phải cùng được xem xét mở rộng
trước, sau đó đến các đỉnh nằm trong đường dẫn bên phải cùng.
Định nghĩa 9 (Cạnh mở rộng). Cho một cạnh giữa hai đỉnh vi, vj và một hàm gán
nhãn φ. Một bộ 5 gồm (vi, vj, φ(vi), φ(vj), φ(vi vj)) biểu diễn cạnh, nhãn đỉnh của 2 đỉnh và
nhãn của cạnh được gọi là cạnh mở rộng.
Định nghĩa 10 (mã DFS). Mã DFS của một đồ thị là một chuỗi các cạnh mở rộng,
được sắp xếp theo thứ tự tìm kiếm theo chiều sâu.
Định nghĩa 11. (Thứ tự tổng thể của các cạnh mở rộng). Gọi t1 và t2 là hai cạnh mở rộng:
t1 = (vi, vj, L(vi), L(vj), L(vi, vj))
t2 = (vx, vy, L (vx), L(vy), L(vx, vy))
Cạnh t1 được cho là nhỏ hơn t2 khi và chỉ khi:
i) (vi, vj) <e (vx, vy);
ii) (vi, vj) =e (vx, vy) và (L(vi), L(vj), L(vi, vj)) <l (L(vx), L(vy), L(vx, vy)).
Mối quan hệ <e phù hợp với quy tắc mở rộng đường dẫn bên phải cùng, nghĩa là đối
với eij = (vi, vj) và exy = (vx, vy) thì eij <e exy khi và chỉ khi:
a) eij và exy đều là các cạnh tiến thì j x;
b) eij và exy đều là các cạnh lùi thì i x;
c) eij là cạnh tiến và exy là cạnh lùi thì j ≤ x;
d) eij là một cạnh lùi và exy là một cạnh tiến thì i<y.
Định nghĩa 12 (mã DFS chuẩn tắc). Mã DFS được gọi là chuẩn tắc khi và chỉ khi nó
có thứ tự nhỏ nhất trong số tất cả mã DFS tương ứng với cùng một đồ thị.
Mỗi đồ thị chỉ có một mã DFS chuẩn tắc, điều này cho phép phát hiện hiệu quả các đồ
con thị trùng lặp. Trong quá trình tìm kiếm các đồ thị con phổ biến, các đồ thị con không
được bỏ qua [5].
Thuật toán TKG thực hiện tìm kiếm theo chiều rộng, sử dụng 02 hàng đợi: hàng đợi Qk
được sử dụng để xác định lại giá trị minSup và hàng đợi Qc được sử dụng để chọn đồ thị
con có độ hỗ trợ lớn nhất để tiến hành mở rộng vì chúng có khả năng mang lại các đồ thị
con có hỗ trợ cao và do đó giúp tăng ngưỡng minSup nhanh hơn để giảm không gian tìm
Nghiên c
Tạp chí Nghi
kiếm. Ban đầu Q
nh
hàng đ
rộng g' đ
rộng g' có độ hỗ trợ không nhỏ h
ngư
Đầu v
Đầu ra:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
4.1. Thu
toán TKG, mô hình c
mã c
ất. Tiếp theo, thuật toán TKG sẽ thực hiện lặp tr
ỡng minSup đ
Thu
ủa thuật toán đ
ợi Q
ào :
Hàng đ
Hàng đ
minSup đư
while (
}
return Q
ật toán song song khai phá Top
ứu khoa học công nghệ
ược mở rộng từ đồ thị g theo đỉnh thuộc đ
CSDL đ
k đ
g = Q
eps= rightMostP athExtensions(g, GD);
foreach
}
ật toán song song ParaTKG
ên c
c khác r
ồ thị con phổ biến
ợi
tr
1 c
ợi
trong đó
kh
Q
g'= g
sup(g’)=sup(t);
if
}
ứu KH&CN
k
ưu tiên Q
ợ nhỏ h
ạnh đ
ưu tiên Q
ởi tạo bằng k độ thị con có 1 cạnh đ
ợc gán bằng độ hỗ trợ của đồ thị con trong đầu h
c is not empty
c. pop();
(sup(g’)
// Lưu g’ vào hàng đ
Insert g' into Q
if
}
// L
Insert g’ into Q
k;
4. Đ
và Q
ỗng, đồ thị
ược xác đ
ồ thị GD, giá trị ng
(t; sup(t))
∪
(Q
if
// Nâng ngư
minsup = sup(Q
ưu g’ vào hàng đ
Ề XUẤT THUẬT TOÁN SONG SONG PARATKG
ư
ơn th
ơn có đ
,
{t};
K.size()
(Q
ủa thực hiện của thuật toán ParaTKG đ
ợc tr
c đều đ
đồ thị con có độ hỗ trợ lớn h
≥ minsup and isCanonical(g’))
K.size() > k)
ình bày trong
Hình 1.
quân s
ịnh lại.
k để l
ì có
c để l
) {
∈
≥ k)
ược khởi tạo bằng k đồ thị con 1 cạnh đ
g có đ
ưu tr
ộ hỗ trợ lớn nhất.
ưu tr
eps
K;
ỡng minSup
c;
ự, Số
ơn minSup th
độ
{
{
k
ợi Q
Mô hình thu
ộ hỗ trợ cao nhất trong Q
ư
ữ k đồ thị con phổ biến, trong đó
ưu tiên cao hơn. Q
ữ các đồ thị con ứng vi
ợi Q
Qk
.peek());
Đặc san Hội thảo Quốc gia FEE, 10
ỡng k.
k
.pop();// Lo
c
-K đ
bảng
ồ thị con phổ biến đ
2.
ật toán ParaTKG
ì g' s
ại bớt đồ thị con thừa
ên hàng đ
ường dẫn phải c
ơn
ơn có đ
ẽ đ
k đư
thì có
{
ược đẩy v
ợc khởi tạo bằng k độ thị con có
ên cho vi
ộ hỗ trợ lớn nhất.
ợi Q
độ
ược tr
c đư
B
ưu tiên cao hơn. Q
àng đ
ược thiết kế dựa tr
.
c. C
ợc lấy ra v
ùng nh
ào hàng đ
ảng 1.
ệc mở rộng tiếp theo,
ình bày trên hình
ơn có đ
ụ thể, trong khi m
, đồ thị con có độ hỗ
ợi của Q
-
ất, nếu đồ thị mở
Thu
2020
ợi Q
ật toán TKG.
ộ hỗ trợ cao
à đ
c
ồ thị mở
k
c
ên thu
441
và Q
được
và gi
à
c,
ật
ả
Toán học – Công nghệ thông tin
P. V. Lai, , P. V. Anh, “Thuật toán song song khai phá Top-K đồ thị con phổ biến.” 442
Bảng 2. Thuật toán ParaTKG.
Đầu vào : CSDL đồ thị GD, giá trị ngưỡng k.
Đầu ra: k đồ thị con phổ biến
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
Hàng đợi ưu tiên Qk để lưu trữ k đồ thị con phổ biến, trong đó, đồ thị con có độ hỗ
trợ nhỏ hơn thì có độ ưu tiên cao hơn. Qk được khởi tạo bằng k đồ thị con có
1 cạnh đơn có độ hỗ trợ lớn nhất.
Hàng đợi ưu tiên Qc để lưu trữ các đồ thị con ứng viên cho việc mở rộng tiếp theo,
trong đó, đồ thị con có độ hỗ trợ lớn hơn thì có độ ưu tiên cao hơn. Qc được
khởi tạo bằng k đồ thị con có 1 cạnh đơn có độ hỗ trợ lớn nhất.
minSup được gán bằng độ hỗ trợ của đồ thị con trong đầu hàng đợi của Qc
while (Qc is not empty) {
foreach Processors {
Task ti = new Task(() {
synchronized (g = Qc. pop(););
eps= rightMostPathExtensions(g, GD);
foreach (t; sup(t)) ∈ eps {
g'= g ∪ {t};
sup(g’)=sup(t);
if (sup(g’) ≥ minsup and isCanonical(g’)) {
// Lưu g’ vào hàng đợi Qk
synchronized (Insert g' into QK;);
if (QK.size() ≥ k) {
if (QK.size() > k) Qk.pop();// Loại bớt đồ thị con thừa
// Nâng ngưỡng minSup
synchronized (minsup = sup(Qk.peek()););
}
// Lưu g’ vào hàng đợi Qc
synchronized (Insert g’ into Qc;);
}
}
}
}
return Qk;
Dòng 1, 2, 3 thực hiện khởi tạo 02 hàng đợi Qk, Qc và xác định minSup ban đầu như
trong thuật toán TKG. Tiếp theo, Qk và Qc là 02 hàng đợi dùng chung, chia sẽ giữa các
nhân xử lý. Thuật toán ParaTKG được thiết kế theo phương pháp cân bằng tải động. Cụ
thể, ở dòng 6, mỗi nhân sẽ nhận một đồ thị con g từ hàng đợi Qc, thực hiện mở thêm 01
cạnh theo đường dẫn phải cùng nhất để xác định đồ thị con phổ biến g' có nhiều hơn g một
cạnh, sau đó cập nhật g' vào Qk, Qc và xác định lại minSup. Việc khai phá ra các đồ thị con
g' từ đồ thị g được thực hiện trong các nhân một cách độc lập, riêng việc cập nhật g' vào
Qk, Qc và xác định lại minSup phải thực hiện theo cơ chế cạnh tranh do Qk, Qc là các hàng
đợi dùng chung.
4.2. Ví dụ minh hoạ
Hình 3 minh hoạ một số bước thực hiện thuật toán song song ParaTKG với 2 luồng
khai phá Top-K đồ thị con phổ biến với k=4 từ CSDL đồ thị gồm 02 đồ thị G1, G2 như
trên hình 2.
Ban đầu, có 04 đồ thị con 1 cạnh đơn được xác định: g1=(0,1,a,a) với sup(g1)=2;
g2=(0,1,a,b) với sup(g2)=2; g3=(0,1,b,a) với sup(g3)=2; g4=(0,1,b,b) với sup(g4)=1;
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Hội thảo Quốc gia FEE, 10 - 2020 443
Loại g3 vì nó là một đẳng cấu của g2.
Qk = {g4, g1, g2};