ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN Hà Nội – 2016 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRANG PHỤ BÌA PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Ngọc Hóa Hà Nội – 2016 LỜI CẢM ƠN Để hoàn thiện luận văn thạc sỹ mình, trước tiên, xin bày tỏ lòng biết ơn sâu tới thầy – PGS.TS Nguyễn Ngọc Hóa (bộ môn Các hệ thống thông tin – trường Đại học Công nghệ – Đại học Quốc gia Hà Nội) Sự gần gũi, khích lệ nhiệt tình hướng dẫn thầy nguồn động lực lớn suốt thời gian thực luận văn Tôi xin gửi lời cảm ơn chân thành tới tất thầy, cô môn Các hệ thống thông tin, thầy, cô khoa Công nghệ thông tin – trường Đại học Công nghệ – Đại học Quốc gia Hà Nội nhiệt tình giảng dạy, cung cấp cho kiến thức, kinh nghiệm không học tập mà sống hàng ngày Đồng thời xin gửi lời cảm ơn đến cha mẹ, người thân gia đình, bạn học viên, đồng nghiệp giúp đỡ, động viên, tạo điều kiện tốt cho suốt khóa học Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội để hoàn thiện tốt luận văn thạc sỹ Hà Nội, tháng 11 năm 2016 Học viên Phạm Hải Đăng LỜI CAM ĐOAN Tôi xin cam đoan luận văn tốt nghiệp “Tối ưu hóa truy vấn tìm đường ngắn đồ thị động quy mô lớn” công trình nghiên cứu thực thân, thực sở nghiên cứu lý thuyết, kiến thức chuyên ngành, nghiên cứu khảo sát tình hình thực tiễn hướng dẫn khoa học PGS.TS Nguyễn Ngọc Hóa Các kết viết chung với tác giả khác đồng ý tác giả trước đưa vào luận văn Những phần tham chiếu, trích dẫn luận văn nêu rõ phần tài liệu tham khảo Các số liệu, kết trình bày luận văn hoàn toàn trung thực Nếu sai xin chịu hoàn toàn trách nhiệm chịu kỷ luật khoa nhà trường đề Hà Nội, tháng 11 năm 2016 Học viên Phạm Hải Đăng MỤC LỤC TRANG PHỤ BÌA LỜI CẢM ƠN LỜI CAM ĐOAN MỤC LỤC DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH VẼ Giới thiệu chung Động lực nghiên cứu Mục tiêu nội dung luận văn Tổ chức luận văn Chương 1: Cơ sở lý thuyết vấn đề liên quan 10 1.1 Đồ thị 10 1.1.1 Giới thiệu đồ thị 13 1.1.2 Một số thuật ngữ 14 1.1.3 Biểu diễn đồ thị 15 1.1.4 Các thuật toán tìm kiếm đồ thị ứng dụng 18 1.2 Bài toán tìm đường ngắn 21 1.3 Tổng kết chương 27 Chương 2: Bài toán, cách tiếp cận phương pháp giải 28 2.1 Định nghĩa toán 28 2.2 Các vấn đề liên quan 29 2.3 Cách tiếp cận giải toán 34 2.4 Cấu trúc liệu phù hợp 34 2.5 Tối ưu trình thêm xóa cạnh đồ thị 37 2.5.1 Thêm cạnh 37 2.5.2 Xóa cạnh 39 2.6 Tối ưu trình xử lý truy vấn tìm đường ngắn 40 2.6.1 Cải thiện thuật toán tìm đường ngắn từ hai hướng 40 2.6.2 Song song hóa truy vấn tìm đường ngắn 41 2.7 Tổng kết chương 41 Chương 3: Thực nghiệm đánh giá 42 3.1 Cài đặt 42 3.2 Thực nghiệm 46 3.2.1 Cuộc thi ACM Sigmod Contest 2016 46 3.2.2 Kiểm nghiệm với liệu SNAP 47 3.3 Tổng kết chương 53 Kết luận chung 54 Các đóng góp 54 Hướng phát triển 54 Danh mục công trình khoa học tác giả 55 Tài liệu tham khảo 56 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu Giải thích Tiếng Anh Tiếng Việt GPS Global Positioning System Hệ thống định vị toàn cầu ACM Association for Computing Machinery Hiệp hội máy tính giới Sigmod Special Interest Group on Management of Data Nhóm quan tâm đặc biệt quản lý liệu DFS Depth First Search Thuật toán duyệt đồ thị theo chiều sâu BFS Breadth First Search Thuật toán duyệt đồ thị theo chiều rộng BBFS Bi-directional Breadth First Search Thuật toán duyệt đồ thị theo chiều rộng từ hai hướng SNAP Stanford Network Analysis Platform Nền tảng phân tích mạng Stanford DANH MỤC CÁC BẢNG Bảng 1.1: Một số thống kê độ phức tạp số phương phức đồ thị [11] 17 Bảng 2.1: Độ trễ nhớ 2016 34 Bảng 3.1:Thống kê liệu ACM Sigmod 46 Bảng 3.2: Kết thi ACM Sigmod (tính theo giây) 46 Bảng 3.3: Thống kê liệu LiveJournal Pokec 49 Bảng 3.4: Kết thử nghiệm (tính theo mili giây) 51 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Mạng xã hội 10 Hình 1.2: Đường mạng xã hội 11 Hình 1.3: Chu trình mạng xã hội 11 Hình 1.4: Bản đồ khoảng cách số tỉnh thành phía Bắc 12 Hình 1.5: Mạng xã hội có hướng 12 Hình 1.6: Đồ thị 13 Hình 1.7: Đồ thị có hướng 15 Hình 2.1: Dữ liệu đầu vào 29 Hình 2.2: Lô liệu kiểm thử 29 Hình 2.3: Giới thiệu OpenMP 31 Hình 2.4: Giới thiệu Pthread 32 Hình 2.5: Song song hóa truy vấn Cilk Plus 33 Hình 2.6: Cấu trúc liệu đồ thị 36 Hình 2.7: Thêm cạnh cách chèn vào mảng 37 Hình 2.8: Cấu trúc liệu danh sách kề cấp phát trước khoảng trống 38 Hình 2.9: Thêm cạnh cách cấp trước khoảng trống 38 Hình 2.10: Quá trình thêm cạnh 39 Hình 2.11: Quá trình xóa cạnh 39 Hình 2.12: Thứ tự duyệt đỉnh thuật toán duyệt đồ thị theo chiều rộng từ hai hướng 40 Hình 3.1: Thời gian thực thi hai phép toán thao tác mảng bit 45 Hình 3.2: Kết thi ACM Sigmod 2016 48 Hình 3.3: Kết thử nghiệm với liệu SIGMOD TEST 52 Hình 3.4: Kết thử nghiệm với liệu POKEC 52 Hình 3.5: Kết thử nghiệm với liệu LIVEJOURNAL 53 Giới thiệu chung Động lực nghiên cứu Hiện nay, sống thời đại bùng nổ công nghệ thông tin bùng nổ xã hội mạng Một số mạng điển mạng xã hội (Facebook, Twitter), mạng sinh học, mạng phân tán nội dung, mạng lưới giao thông, mạng thông tin… có số lượng liệu tăng nhanh chóng mặt Để giải thách thức mặt liệu lớn trên, có nhiều phương pháp tiếp cận, phương pháp tiếp cận dựa đồ thị cho trực quan phù hợp [8] Với việc sử dụng lý thuyết đồ thị, đỉnh biểu diễn thực thể cạnh biểu diễn mối liên hệ chúng Trong đồ thị, tìm đường (ngắn nhất) vấn đề tìm kết nối hai đỉnh đồ thị đảm bảo đường ngắn dựa số yêu cầu cho trước Đây vấn đề tảng áp dụng nhiều ứng dụng thực tế tìm đường ngắn hai địa điểm sử dụng GPS hay tìm mối liên kết hai người mạng xã hội [6] Vấn đề bình thường đơn giản, bối cảnh số lượng đỉnh, cạnh đồ thị lớn (vài triệu đỉnh) thay đổi nhanh (thêm cạnh, bớt cạnh), làm để tối ưu hóa trình tìm đường ngắn thách thức lớn [21] Mục tiêu nội dung luận văn Với mục tiêu trên, luận văn trình bày giải pháp để cải thiện hiệu trình tối ưu truy vấn đồ thị động, quy mô lớn có hướng không trọng số Phương pháp tối ưu dựa ý tưởng: cấu trúc liệu phù hợp, tối ưu không gian tìm kiếm cài đặt phù hợp Tổ chức luận văn Nội dung luận văn tổ chức sau: Mở đầu: Đặt vấn đề Chương 1: Giới thiệu sở lý thuyết, vấn đề liên quan đến đồ thị toán tìm đường ngắn đồ thị Chương 2: Trình bày toán, cách tiếp cận, phương pháp giải toán Chương 3: Thực nghiệm đánh giá kết đạt Kết luận chung: Kết luận đưa hướng phát triển 43 Thủ tục 2: Thêm cạnh (u, v) vào đồ thị G Để tích hợp trình song song hóa tìm khoảng cách ngắn nhất, trước thực xóa cạnh, tất truy vấn tìm đường ngắn danh sách trước thực Thủ tục xóa cạnh (u, v) đồ thị G mô tả Thủ tục 3: Xóa cạnh (u, v) đồ thị G Thủ tục quan trọng tìm đường ngắn hai đỉnh (u, v) dựa thuật toán duyệt đồ thị theo chiều rộng từ hai hướng cải tiến sử dụng hai mảng đỉnh vào (incoming_array) đỉnh (outgoing_array) Quá trình mô tả cụ thể Thủ tục 44 Thủ tục 4: Tìm đường ngắn hai đỉnh (u, v) theo phương pháp duyệt đồ thị theo chiều rộng từ hai hướng cải tiến Trong thuật toán duyệt đồ thị theo chiều rộng (mục 1.1.4), có bước đánh dấu đỉnh duyệt Để đánh dấu đỉnh này, thuật toán cài đặt theo mã giả giới thiệu (mục 1.1.4) Khi đó, để đánh dấu đỉnh xét/chưa xét cần khởi tạo mảng số lượng đỉnh đồ thị Ví dụ đồ thị triệu cạnh, cần có mảng triệu phần tử Với phần tử kiểu chiếm dung lượng byte nhớ, không gian lưu 45 trữ mảng byte * 1.000.000 = 4.000.000 byte ~ megabyte nhớ Tuy nhiên, thao tác trực tiếp đến bit, dùng thứ tự bit để đánh dấu đỉnh đồ thị, đỉnh chưa xét giá trị bit 0, đỉnh xét giá trị bit Khi không gian lưu trữ mảng đánh dấu đồ thị có triệu 1.000.000 bit ~ 125.000 byte ~ 0.125 megabyte nhớ Như vậy, không gian nhớ giảm 32 lần Điều cần thiết thao tác với đồ thị quy mô liệu lớn Mặt khác, cài đặt mảng đánh dấu theo kiểu truy xuất đến bit, phép toán bit nhanh nhiều so với phép toán phần tử mảng Đồ thị Hình 3.1 miêu tả chi tiết thời gian thực thi hai phép toán thao tác mảng thao tác bit Trong đồ thị, số lượng phép toán bao gồm tổng số lần gán phần tử (một bit) số lần kiểm tra xem phần tử gán hay chưa Thời gian thực thi hai phép toán thao tác mảng bit milisecond 1000 10000 100000 Số lượng phép toán Bit Array Hình 3.1: Thời gian thực thi hai phép toán thao tác mảng bit Cuối cùng, Cilk Plus dùng để song song hóa thủ tục tìm đường ngắn hai đỉnh (u, v) Thủ tục 5: Xử lý song song truy vấn liên tiếp đồ thị G 46 3.2 Thực nghiệm 3.2.1 Cuộc thi ACM Sigmod Contest 2016 Trong thi này, liệu đồ thị lớn dùng để đánh giá giải pháp đội Mỗi bao gồm tập trình thêm cạnh, xóa cạnh, truy vấn tìm đường ngắn liên tục Bảng 3.1 thống kê chi tiết thông số liệu kiểm tra ACM Sigmod Bảng 3.1:Thống kê liệu ACM Sigmod Thông số Small Medium X-Large XX-Large Đỉnh 574 074 000 000 971 281 009 555 Cạnh 232 855 000 000 533 214 16 518 948 Bậc lớn 114 557 90 412 12 779 Bậc lớn 114 125 356 364 12 770 Dựa quy định ban tổ chức, tất giải pháp đội kiểm nghiệm máy tính có cấu sau: + CPU: x Intel E5-2620v2 (12 cores / 24 threads) + RAM: 20GB + Hệ điều hành: Ubuntu 14.04 Linux + Phần mềm: Automake 1.15, gcc5.2.1 Dưới kết giải pháp cài đặt ngôn ngữ lập trình C: Bảng 3.2: Kết thi ACM Sigmod (tính theo giây) Đội Bộ liệu Small Medium X-Large XX-Large 0.118 0.494 1.284 2.878 0.107 0.220 0.886 2.333 akgroup (giải pháp luận văn/đồng giải ba) H_minor_free (giải nhất) 47 uoa_team (giải nhì) while1 (đồng giải ba) gStreamPKU (đồng giải ba) 0.208 0.217 1.085 2.123 0.157 0.234 1.150 2.597 0.134 0.072 1.087 3.239 Với kết trên, giải pháp lựa chọn năm đội xuất sắc thi lập trình ACM Sigmod 2016 (Hình 3.2) mời đến trình bày kết hội nghị Sigmod 2016 3.2.2 Kiểm nghiệm với liệu SNAP Hai liệu phù hợp với mô hình chọn LiveJournal Pokec Trong LiveJournal liệu cộng đồng trực tuyến miễn phí với gần 10 triệu thành viên, lượng đáng kể số lượng thành viên thường xuyên hoạt động (có khoảng 300.000 cập nhật/ngày) LiveJournal cho phép thành viên trì tạp chí, blog cá nhân nhóm Nó cho phép người cộng đồng tự kết bạn với [5] Pokec liệu mạng xã hội trực tuyến phổ biến Slovakia Mặc dù Facebook phát triển đây, số lượng người dùng Pokec ổn định Mạng xã hội Pokec triển khai 10 năm có khoảng 1,6 triệu người kết nối Bộ liệu bao gồm liệu người dùng (ẩn danh) toàn mạng Nó bao gồm giới tính, tuổi, sở thích, giáo dục… Thông tin cung cấp dạng ngôn ngữ Slovakia Kết nối mạng xã hội có hướng [5] 48 Hình 3.2: Kết thi ACM Sigmod 2016 49 Chi tiết hai liệu miêu tả Bảng 3.3 Bảng 3.3: Thống kê liệu LiveJournal Pokec Thông số LiveJournal Pokec Đỉnh 847 571 632 803 Cạnh 68 993 773 30 622 564 Độ dài khoảng cách lớn 16 11 Bậc lớn 20 293 763 Bậc lớn 13 906 13 733 Cấu hình máy thử nghiệm + CPU: x Intel Xeon E7- 4850 @ 2.00GHz (10 cores / 20 threads) + RAM: 128GB + Hệ điều hành: CentOS 6.7 Linux + Phần mềm: Automake 1.15, gcc5.2.0 Khối lượng kiểm nghiệm Để kiểm nghiệm phương pháp, công cụ sinh tự động kiện xây dựng theo phương pháp trình bày mục 2.1 Với đồ thị, sinh kiểm thử với khoảng 1.000.000 kiện Tỉ lệ kiện truy vấn/thêm cạnh/xóa cạnh tương ứng 8/1/1 Thực chất, có khoảng 800.000 truy vấn tìm đường ngắn nhất, 100.000 kiện thêm cạnh 100.000 kiện xóa cạnh Kết thử nghiệm Thuật toán trình bày luận văn so sánh với hai giải pháp Reference, Snap trình bày mục 2.2, với giải pháp thi ACM Sigmod Contest 2016 Trong giải pháp Reference, đồ thị lưu trữ dạng danh sách liền kề theo kiểu dictionary ngôn ngữ lập trình python Mỗi kiện thêm cạnh xóa cạnh thực Sự kiện truy vấn sử dụng thuật toán tìm kiếm tìm đường ngắn từ hai hướng Còn giải pháp Snap, đồ thị 50 lưu trữ dạng danh sách liền kề theo cấu trúc liệu vector ngôn ngữ lập trình C++ Hai kiện thêm cạnh xóa cạnh thực Sự kiện truy vấn sử dụng thuật toán tìm đường ngắn từ hai hướng Thêm nữa, giải pháp bốn đội xuất sắc thi ACM Sigmod 2016 sử dụng để so sánh Dưới tóm tắt giải pháp bốn đội H_minor_free (đội đạt giải nhất): Lưu trữ đồ thị dạng danh sách cạnh liền kề theo cấu trúc vector ngôn ngữ C++ Mỗi cạnh gán thêm thuộc tính ALIVE: cạnh qua, DEAD: cạnh qua, UNKNOWN: cạnh thay đổi trình thực lô Với lô, thuật toán thực qua ba bước - Bước 1: Với cạnh thêm vào xóa thay đổi thuộc tính cạnh thành UNKNOWN - Bước 2: Sử dụng thuật toán duyệt đồ thị theo chiều rộng từ hai hướng sử dụng OpenMP để song song truy vấn - Bước 3: Thay đổi thuộc tính cạnh thành ALIVE (sự kiện thêm cạnh), DEAD (sự kiện xóa cạnh) sau trình truy vấn Uoa_team (đội đạt giải nhì): Đồ thị biểu diễn dạng danh sách kề, gồm danh sách kề đỉnh vào danh sách kề đỉnh Các kiện thêm cạnh xóa cạnh không thực song song mà lưu cấu trúc liệu khác với phiên Sự kiện truy vấn sử dụng thuật toán duyệt đồ thị theo chiều rộng từ hai hướng kết hợp với phương pháp threadpool để tăng tốc trình truy vấn While1: Đồ thị biểu diễn dạng hai danh sách kề đỉnh đỉnh vào Mỗi kiện thêm cạnh xóa cạnh thêm vào danh sách transaction Sau kết thúc lô, transaction áp dụng để thêm cạnh xóa cạnh từ đồ thị Chương trình sử dụng nhiều luồng để tăng tốc xử lý kiện Luồng xử lý kiện thêm, xóa cạnh Sự kiện truy vấn sử dụng thuật toán duyệt đồ thị theo chiều rộng từ hai hướng phân phối cho luồng lại gStreamPKU: Lưu trữ đồ thị dạng danh sách cạnh liền kề theo cấu trúc unordered_map ngôn ngữ C++ Một đồ thị tạm gọi Delta Graph xây dựng để lưu kiện thêm cạnh xóa cạnh với nhãn thời gian kiện Thuật toán duyệt đồ thị theo chiều rộng từ hai hướng sử dụng kiện truy vấn kết hợp với Threading Building Blocks (TBB) để tăng tốc trình truy vấn 51 Để đánh giá hiệu thuật toán, phương pháp chạy tổng cộng lần, sau lấy kết trung bình Đối với giải pháp luận văn đội thi ACM Sigmod 2016, chương trình thực thi với 24 luồng (giống điều kiện máy kiểm thử ban tổ chức) Kết trung bình trình bày chi tiết Bảng 3.4 Bảng 3.4: Kết thử nghiệm (tính theo mili giây) Bộ liệu Sigmod Test Pokec Live Journal 787 17 985 42 876 825 674 903 068 53 235 981 Snap 48 741 49 316 108 ~ ngày H_minor_free 422 047 15 673 Uoa_team 110 17 526 14 724 Kết truy vấn chưa xác Kết truy vấn chưa xác Kết truy vấn chưa xác 918 134 12 085 Giải pháp Giải pháp luận văn Reference While1 gStreamPKU Bên cạnh đó, luận văn so sánh phương pháp giải pháp thay đổi số lượng luồng xử lý truy vấn Kết chi tiết miêu tả Hình 3.3, Hình 3.4 Hình 3.5 52 SIGMOD TEST 8000 7000 Milliseconds 6000 5000 4000 3000 2000 1000 16 24 32 48 Number of Threads Thesis H_miror_free uoa_team gStreamPKU Hình 3.3: Kết thử nghiệm với liệu SIGMOD TEST POKEC 70000 60000 Milliseconds 50000 40000 30000 20000 10000 16 24 32 Number of Threads Thesis H_miror_free uoa_team gStreamPKU Hình 3.4: Kết thử nghiệm với liệu POKEC 48 53 LIVEJOURNAL 140000 Milliseconds 120000 100000 80000 60000 40000 20000 16 24 32 48 Number of Threads Thesis H_miror_free uoa_team gStreamPKU Hình 3.5: Kết thử nghiệm với liệu LIVEJOURNAL Dựa kết thu được, rút kết luận, tùy thuộc vào liệu mà trình song song hóa có hiệu hay không Bộ liệu Sigmod có số lượng đỉnh có bậc bậc lớn Nói cách khác, số đỉnh tập trung đến, tập trung từ vài đỉnh, không phân bố đồ thị Hệ số lượng đỉnh treo nhiều Do đó, truy vấn tìm đường ngắn thực thi nhanh Khi đó, chi phí cho việc quản lý nhiều luồng không bù lại chi phí thi hành song song hóa Bởi vậy, trường hợp số lượng luồng cho kết tốt Ngược lại, hai liệu LiveJournal Pokec có quy mô liệu đồ sộ nhiều lần so với liệu Sigmod (gấp khoảng 25 10 lần), có tỉ lệ đỉnh/cạnh lớn (3/4 1/2), kết hợp với cạnh phân bố hơn, đó, trình song song hóa thực có tác dụng Tuy nhiên, việc tăng số lượng luồng lên đến mức định Quá giới hạn này, chương trình gặp phải vấn đề chi phí quản lý luồng đề cập Vì vậy, với liệu, phải dựa vào thực tế để tìm ngưỡng luồng đạt hiệu cao 3.3 Tổng kết chương Chương trình bày chi tiết phương án cài đặt dựa phân tích chương Bên cạnh đó, luận văn so sánh kết thực nghiệm với hai thư viện NetworkX Snap, so sánh cụ thể với bốn đội đạt kết tốt thi lập trình ACM Sigmod 2016 Kết thu cho phép kết luận phương án luận văn đạt hiệu tốt 54 Kết luận chung Các đóng góp Sau thời gian nghiên cứu tìm hiểu đề tài, luận văn hoàn thành đạt nội dung đề với mục tiêu tối ưu truy vấn tìm đường ngắn đơn đồ thị, động, có hướng, không trọng số với quy mô liệu lớn Về lý thuyết, luận văn trình bày số kiến thức đồ thị, dạng đồ thị ứng dụng lý thuyết đồ thị toán cụ thể đời sống hàng ngày Tiếp theo, luận văn trình bày bốn mô hình liên quan đến việc cài đặt đồ thị thực tế phân tích ưu, nhược điểm mô hình Bên cạnh đó, luận văn trình bày toán tìm đường ngắn đồ thị, thuật toán hay sử dụng ứng dụng toán thực tiễn Kế tiếp, luận văn trình bày công cụ mã nguồn mở, vấn đề liên quan xử lý toán liên quan đến đồ thị, kết hợp với đánh giá mặt thuận lợi khó khăn áp dụng với đơn đồ thị, động, có hướng, không trọng số với quy mô liệu lớn Về thực nghiệm, luận văn đưa phương pháp để cải thiện trình tìm đường ngắn nhất, cài đặt hoàn chỉnh mã nguồn ngôn ngữ C Phương pháp kiểm nghiệm thi lập trình ACM Sigmod 2016 cho kết khả quan Thêm vào đó, thuật toán luận văn so sánh với số công cụ mã nguồn mở cho xử lý toàn liên quan đến đồ thị tốt với bốn đội xuất sắc từ thi lập trình ACM Sigmod 2016 hai LiveJournal Pokec Kết cho thấy phương pháp đạt kết tốt dựa việc sử dụng cấu trúc liệu phù hợp, tối ưu thuật toán duyệt đồ thị theo chiều rộng từ hai hướng, sử dụng công cụ Cilk Plus để song song hóa trình truy vấn Hướng phát triển Dựa đó, hướng phát triển đề tài tối ưu hóa thuật toán, áp dụng phương pháp khác vào trình tìm kiếm đường ngắn tính toán trước hay dự kiến đường ngắn hai đỉnh qua số đỉnh trung gian Từ giảm nhiều thời gian tính toán lần lại phải tính toán lại từ đầu đường ngắn Tiếp theo áp dụng kỹ thuật giảm tỉ lệ cache miss CPU cho toán cần hiệu cao khác xử lý giao dịch trực tuyến (Online Transaction Processing) 55 Danh mục công trình khoa học tác giả Phuong-Hanh DU, Hai-Dang PHAM, Ngoc-Hoa NGUYEN, "Optimizing the Shortest Path Query on Large-Scale Dynamic Directed Graph", Proceedings of the 3rd IEEE/ACM International Conference on Big Data Computing Applications and Technologies (BDCAT 2016), Shanghai, China, 2016 (Accepted) 56 Tài liệu tham khảo Tiếng Việt [1] Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Toán rời rạc.: Nhà xuất Đại học Quốc gia Hà Nội, 2006 Tiếng Anh [2] Dip Sankar Banerjee, Shashank Sharma, and Kishore Kothapalli, "Work efficient parallel algorithms for large graph exploration," in 20th Annual International Conference on High Performance Computing, 2013, pp 433 - 442 [3] Venkatesan T Chakaravarthy, Fabio Checconi, Fabrizio Petrini, and Yogish Sabharwal, "Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems," in Parallel and Distributed Processing Symposium, 2014 IEEE 28th International, 2014, pp 889 - 901 [4] Cilk Plus [Online] https://www.cilkplus.org [5] Stanford Large Network Dataset http://snap.stanford.edu/data/index.html [6] The ACM SIGMOD Programming http://dsg.uwaterloo.ca/ sigmod16contest/ Collection Contest (2016) [Online] [Online] [7] Tom Cormen and Devin Balkcom KHANACADEMY [Online] https://www.khanacademy.org/computing/computer-science/algorithms/ [8] Jayanta Mondal and Amol Deshpande, "Managing large dynamic graphs efficiently," in ACM SIGMOD International Conference on Management of Data, 2012, pp 145-156 [9] Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin, "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs," in OSDI'12 Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation, 2012, pp 17-30 [10] Joseph E Gonzalez et al., "GraphX: Graph Processing in a Distributed Dataflow Framework," in OSDI'14 Proceedings of the 11th USENIX conference on Operating Systems Design and Implementation, 2014, pp 599-613 [11] Michael T Goodrich, Roberto Tamassia, and Michael H Goldwasser, Data Structures and Algorithms in Java, 6th ed United States of America: Wiley, 2014 57 [12] Aric A Hagberg, Daniel A Schult, and Pieter J Swar, "Exploring network structure, dynamics, and function using NetworkX," in Proceedings of the 7th Python in Science Conference (SciPy), 2008, pp 11-15 [13] Charles E Leiserson and Tao B Schardl, "A work-efficient parallel breadthfirst search algorithm (or how to cope with the nondeterminism of reducers)," in Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, 2010, pp 303-314 [14] Qingxia Li and Wenhong Wei, "A parallel single-source shortest path algorithm based on bucket structure," in 2013 25th Chinese Control and Decision Conference (CCDC), 2013, pp 3445 - 3450 [15] Waqas Nawaz, Kifayat-Ullah Khan, and Young-Koo Lee, "CORE Analysis for Efficient Shortest Path Traversal Queries in Social Graphs," in In Social Graphs,Big Data and Cloud Computing (BdCloud), 2014 IEEE Fourth International Conference, Sydney, 2014, pp 363-370 [16] NetworkX [Online] http://networkx.github.io [17] Open Multi-Processing [Online] http://openmp.org/ [18] POSIX Threads Programming https://computing.llnl.gov/tutorials/pthreads/ [Online] [19] Grégoire Scano, Marie-José Huguet, and Sandra Ulrich Ngueveu, "Adaptations of k-shortest path algorithms for transportation networks," in Industrial Engineering and Systems Management (IESM), 2015 International Conference on, 2015, pp 663 - 669 [20] Stanford Network Analysis Platform [Online] http://snap.stanford.edu [21] Leong Hou U, Hong Jun Zhao, Man Lung Yiu, Yuhong Li, and Zhiguo Gong, "Towards Online Shortest Path Computation," IEEE Transactions on Knowledge and Data Engineering, vol 26, no 4, pp 1012 - 1025, Apr 2014 [22] Jian Wei, Kai Chen, Yi Zhou, Qu Zhou, and Jianhua He, "Benchmarking of Distributed Computing Engines Spark and GraphLab for Big Data Analytics," in 2016 IEEE Second International Conference on Big Data Computing Service and Applications (BigDataService), 2016, pp 10 - 13 ... GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRANG PHỤ BÌA PHẠM HẢI ĐĂNG TỐI ƯU HÓA TRUY VẤN TÌM ĐƯỜNG NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG QUY MÔ LỚN Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã... cạnh 39 2.6 Tối ưu trình xử lý truy vấn tìm đường ngắn 40 2.6.1 Cải thiện thuật toán tìm đường ngắn từ hai hướng 40 2.6.2 Song song hóa truy vấn tìm đường ngắn 41 2.7 Tổng... chúng Trong đồ thị, tìm đường (ngắn nhất) vấn đề tìm kết nối hai đỉnh đồ thị đảm bảo đường ngắn dựa số yêu cầu cho trước Đây vấn đề tảng áp dụng nhiều ứng dụng thực tế tìm đường ngắn hai địa