Luận án tiến sĩ nâng cao hiệu năng thi hành các phép toán trên đồ thị

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Dư Phương Hạnh NÂNG CAO HIỆU NĂNG THI HÀNH CÁC PHÉP TOÁN TRÊN ĐỒ THỊ LUẬN ÁN TIẾN SỸ HỆ THỐNG THÔNG TIN Hà Nội - 2019 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Dư Phương Hạnh NÂNG CAO HIỆU NĂNG THI HÀNH CÁC PHÉP TOÁN TRÊN ĐỒ THỊ LUẬN ÁN TIẾN SỸ HỆ THỐNG THÔNG TIN Chuyên ngành: Hệ thống thông tin Mã số: 9480104.01 Người hướng dẫn khoa học: 1. Nguyễn Hải Châu 2. Nguyễn Kim Khoa Hà Nội - 2019 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LỜI CẢM ƠN Luận án được thực hiện tại Trường Đại học Công nghệ - ĐHGQ Hà Nội, dưới sự hướng dẫn của PGS. Nguyễn Hải Châu và PGS.

Nguyễn Kim Khoa (Trường ETS - Đại học Quebec - Canada). Trước hết, tôi xin được bày tỏ lòng biết ơn sâu sắc tới PGS. Nguyễn Hải Châu và PGS. Nguyễn Kim Khoa, những người đã hướng dẫn, đưa ra những định hướng giúp tác giả hoàn thành bản luận án này.

Tôi cũng chân thành cám ơn toàn thể các thầy, cô đồng nghiệp trong Bộ môn Các hệ thống thông tin đã đồng hành trong nhiều năm, góp nhiều ý kiến quan trọng để tác giả có thể hoàn thiện các nội dung khoa học của luận án. Để có được kết quả ngày hôm nay, tôi cũng xin chân thành cảm ơn Trường Đại học Công nghệ, Khoa Công nghệ Thông tin, các Phòng chức năng của Trường, đã tạo điều kiện thuận lợi cho tôi trong quá trình nghiên cứu và công tác tại Trường. Sau cùng, tôi xin chân thành cảm ơn gia đình, những người thân và bạn bè đã giúp đỡ, động viên tôi trong suốt thời gian thực hiện luận án này! Hà Nội, tháng 08 năm 2019 Dư Phương Hạnh i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các nội dung viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào Luận án.

Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào khác. Tác giả Dư Phương Hạnh ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Mục lục 1 GIỚI THIỆU CHUNG 1 1.1 Động lực nghiên cứu .1 Cấu trúc dữ liệu phù hợp để nâng cao hiệu năng thi hành các phép toán trên đồ thị .2 Xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn 2 1.3 Nâng cao hiệu năng tính các độ đo quan trọng trong phân tích đồ thị quy mô lớn .2 Một số nghiên cứu liên quan .3 Mục tiêu, phạm vi nghiên cứu, đóng góp và bố cục của luận án .1 Mục tiêu nghiên cứu .2 Phạm vi và phương pháp nghiên cứu .4 Các đóng góp chính của luận án .5 Tổ chức của luận án .3 Các đặc điểm chính của đồ thị .2 Biểu diễn đồ thị .1 Danh sách các cạnh .2 Ma trận liền kề .3 Danh sách liền kề .4 Ma trận liên thuộc .5 Ma trận hàng thưa nén .3 Các phép toán chính trên đồ thị .1 Duyệt theo chiều rộng trước - BFS .2 Duyệt theo chiều sâu trước - DFS .2 Phân tích đồ thị. 26 iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC iv 2.1 Tính khoảng cách .2 Đường đi ngắn nhất .4 Phân cụm đồ thị .4 Tính toán song song .1 Kiến trúc hệ thống tính toán song song .1 Kiến trúc bộ nhớ chia sẻ .2 Kiến trúc bộ nhớ phân tán .3 Kiến trúc bộ nhớ lai chia sẻ-phân tán .2 Mô hình lập trình song song .3 Một số bài toán song song điển hình .5 Kết chương 2. 40 3 TỐI ƯU HOÁ TRUY VẤN KHOẢNG CÁCH NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG 42 3.2 Đặc tả bài toán .1 Mô hình dữ liệu và truy vấn .2 Bài toán tối ưu hoá truy vấn khoảng cách ngắn nhất trên đồ thị động 45 3.3 Cách tiếp cận giải quyết bài toán đặt ra .3 Giải pháp 1: akGroup .1 Cấu trúc dữ liệu đồ thị phù hợp .2 Tối ưu hoá các phép toán cập nhật .1 Thêm cạnh mới .2 Xoá một cạnh .3 Tối ưu các truy vấn .1 Giải thuật tính khoảng cách ngắn nhất .2 Xử lý song song truy vấn .4 Đánh giá thuật toán .4 Giải pháp 2: akGroupPlus .1 Tổ chức dữ liệu đồ thị kèm trạng thái .2 Xử lý các phép toán tương tranh .3 Tối ưu hoá các phép toán cập nhật .4 Tối ưu hoá các truy vấn tính khoảng cách ngắn nhất .1 Giải thuật tính khoảng cách ngắn nhất .2 Xử lý song song truy vấn .5 Đánh giá thuật toán .5 Giải pháp 3: bigGraph.

67 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC v 3.1 Ý tưởng chính .2 Giải thuật song song hoá các phép toán cập nhật .3 Đánh giá thuật toán .6 Thực nghiệm và đánh giá .1 Môi trường và dữ liệu thực nghiệm .1 Môi trường thử nghiệm, đánh giá .2 Dữ liệu thực nghiệm .1 Dữ liệu từ cuộc thi SigMod Programming Contest 2016 .2 Dữ liệu SNAP .2 Phương pháp thử nghiệm, đánh giá .1 Sinh các tập lịch thi hành thử nghiệm .2 Phương pháp đo .3 Thử nghiệm và đánh giá kết quả .1 Kết quả từ cuộc thi ACM SigMod Programming Contest 2016 75 3.2 Đánh giá giải pháp akGroup .3 Đánh giá giải pháp akGroupPlus .4 Đánh giá giải pháp bigGraph .7 Kết chương 3. 88 4 NÂNG CAO HIỆU NĂNG TÍNH ĐỘ TRUNG TÂM TRÊN ĐỒ THỊ 91 4.2 Bài toán đặt ra .1 Tính độ trung tâm gần .2 Tính độ trung tâm trung gian .3 Nâng cao hiệu năng tính độ trung tâm .1 Cấu trúc dữ liệu phù hợp .2 Giải thuật song song tính độ trung tâm gần .3 Giải thuật song song tính độ trung tâm trung gian .4 Thực nghiệm và đánh giá .1 Môi trường thử nghiệm, đánh giá .2 Dữ liệu thực nghiệm .3 Kết quả thực nghiệm và đánh giá .1 Giải pháp nâng cao hiệu năng tính độ trung tâm gần .2 Giải pháp nâng cao hiệu năng tính độ trung tâm trung gian 105 4.5 Kết chương 4. 109 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 110 5.1 Các đóng góp chính .2 Hạn chế của luận án. 112 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC vi 5.3 Hướng phát triển tương lai.

113 DANH MỤC CÁC CÔNG BỐ CỦA LUẬN ÁN 114 TÀI LIỆU THAM KHẢO 115 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh sách hình vẽ 1.1 Lược đồ tổ chức luận án .1 Minh họa về đồ thị xã hội .2 Minh họa việc xuất bản thông điệp .3 Một số kiểu đồ thị cơ bản .4 Đồ thị có hướng và ma trận liền kề .5 Danh sách liền kề .6 Ma trận liên thuộc biểu diễn đồ thị .7 Ma trận hàng thưa nén .8 Ví dụ về duyệt theo chiều rộng trước .9 Ví dụ về duyệt theo chiều sâu trước .10 Một số độ đo trung tâm điển hình trên đồ thị .11 Ảnh hưởng của số CPU và tỷ lệ đoạn mã được song song đến hệ số tăng tốc 34 2.12 Kiến trúc hệ thống tính toán song song dựa trên bộ nhớ chia sẻ .13 Kiến trúc hệ thống tính toán song song dựa trên bộ nhớ phân tán .14 Kiến trúc hệ thống tính toán song song dựa trên bộ nhớ lai chia sẻ-phân tán 37 2.15 Mô hình xử lý song song trong CilkPlus .1 Các phép toán tương tranh trên đồ thị .2 Minh hoạ cấu trúc dữ liệu đồ thị .3 Phép toán bổ sung thêm cạnh trên đồ thị .4 Thi hành phép toán xoá cạnh trong đồ thị .5 Duyệt hai chiều BFS để tính khoảng cách ngắn nhất .6 Thi hành các phép toán tương tranh có thể hiện trạng thái .7 Song song các phép toán cập nhật đồ thị .8 Kết quả đánh giá với bộ dữ liệu Sigmod Dataset .9 Kết quả đánh giá với bộ dữ liệu Pokec Dataset .10 Kết quả đánh giá với bộ dữ liệu LiveJournal Dataset .11 Kết quả thực nghiệm với bộ dữ liệu SigMod 8-1-1 .12 Kết quả thực nghiệm với bộ dữ liệu Sigmod 5-4-1 .13 Kết quả thực nghiệm với bộ dữ liệu Pokec 8-1-1. 84 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH SÁCH HÌNH VẼ viii 3.14 Kết quả thực nghiệm với bộ dữ liệu Pokec 5-4-1 .15 Kết quả thực nghiệm với bộ dữ liệu LiveJournal 8-1-1 .16 Kết quả thực nghiệm với bộ dữ liệu LiveJournal 5-4-1 .1 Thời gian thi hành bigGraph khi tính độ trung tâm trung gian .2 Đánh giá hệ số tăng tốc bigGraph khi tính độ trung tâm trung gian .3 Thời gian thi hành thực nghiệm tính độ trung tâm gần .4 Thời gian thi hành tính độ đo BC của bigGraph (giây) .5 Đánh giá hệ số tăng tốc tính độ đo BC của bigGraph .6 Thời gian thi hành thực nghiệm tính độ đo BC. 108 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh sách bảng 3.1 Thời gian thao tác bộ nhớ .2 Thống kê các đồ thị sử dụng trong SigMod 2016 .3 Thống kê các bộ dữ liệu đồ thị sử dụng trong thực nghiệm .4 Kết quả thực nghiệm trên hệ thống đánh giá của ACM SigMod 2016 (giây) .5 Kết quả đánh giá giải pháp akGroup so với một số công cụ khác .6 Thống kê hiệu năng tốt nhất .1 Thông tin thống kê về các dữ liệu mạng xã hội thử nghiệm .2 Thời gian (giây) và hệ số tăng tốc của bigGraph khi tính độ trung tâm gần .3 Thời gian tính độ trung tâm gần (giây) .4 Hệ số tăng tố của bigGraph so với TeexGraph và NetworKit khi tính độ trung tâm gần .5 Thời gian (giây) và hệ số tăng tốc của bigGraph khi tính độ trung tâm trung gian .6 Thời gian tính độ đo BC (giây) .7 Hệ số tăng tốc của bigGraph so với TeexGraph và NetworKit khi tính độ đo BC. 108 ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh sách thuật toán 2.1 BF S(G, v): Mã giả phương pháp duyệt theo chiều rộng trước .2 DF S(G, v): Mã giả phương pháp duyệt theo chiều sâu trước .3 Giải thuật tính khoảng cách ngắn nhất sử dụng bBFS .1 akGroup: Giải thuật thi hành lịch S .2 akGroup: Thêm cạnh (u, v) vào đồ thị G .3 akGroup: Xoá cạnh (u, v) trong đồ thị G .4 akGroup: Giải thuật tính khoảng cách ngắn nhất (u, v) .5 akGroup: Thi hành song song các truy vấn tính khoảng cách ngắn nhất trong G 57 3.6 akGroupPlus: Giải thuật thi hành lịch S .7 akGroupPlus: Cập nhật các cạnh trong lịch S .8 akGroupPlus: Ghi nhận các phép toán cập nhật .9 akGroupPlus: Tính khoảng cách ngắn nhất giữa (u, v) .10 akGroupPlus: Kiểm tra một cạnh (u, v) có được ghi nhận ở thời điểm t hay không .11 akGroupPlus: Thi hành song song các truy vấn khoảng cách ngắn nhất trên đồ thị G .