Thuật toán song song khai phá Top-K đồ thị con phổ biế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};