CHƯƠNG 1. GIỚI THIỆU CHUNG • Nhóm nghiên cứu hệ thống CSDL (Database Systems)13 của trường Đại học Wisconsin- Madison, Mỹ, với những nghiên cứu về các hệ quản trị CSDL mới, khoa học dữ liệu, trong đó có những nghiên cứu về ứng dụng lý thuyết đồ thị trong quản trị dữ liệu. • Trung tâm nghiên cứu về toán dữ liệu lớn (Global Research Center for BigData Math- ematics)14 của Viện quốc gia tin học Nhật Bản (NII), với những nghiên cứu chuyên sâu về các mạng xã hội quy mô lớn để đề xuất những giải thuật phân tích đồ thị với tốc độ xử lý và có tính sáng tạo cao. • Phòng thí nghiệm về giải thuật Web (Laboratory for Web Algorithms)15 của trường Đại học Milano, Ý, với những nghiên cứu về xử lý và phân tích các đồ thị Web, mạng xã hội.
Đây cũng là nơi tập hợp được nhiều nguồn dữ liệu liên quan đến các mạng xã hội và cung cấp công khai cho cộng đồng.3 Mục tiêu, phạm vi nghiên cứu, đóng góp và bố cục của luận án Với thực trạng đã đặt ra, trong luận án này chúng tôi quan tâm đến bài toán nghiên cứu đề xuất phương pháp tổ chức dữ liệu đồ thị phù hợp kết hợp cùng với những giải pháp song song hoá các phép toán trên đồ thị quy mô lớn cả về số cạnh lẫn số đỉnh để có thể tiến hành xử lý các truy vấn và phân tích trên đồ thị một cách hiệu quả nhất. Các phép toán được quan tâm trên đồ thị gồm những phép toán truy vấn khoảng cách ngắn nhất (với đồ thị động) và những phép tính độ đo trung tâm trong phân tích đồ thị (với đồ thị tĩnh).1 Mục tiêu nghiên cứu Từ bài toán đặt ra, mục tiêu chính của luận án là khảo sát, đánh giá các giải pháp hiện đại về xử lý các phép toán đồng thời trên đồ thị quy mô lớn; từ đó đề xuất phương pháp tổ chức dữ liệu đồ thị phù hợp và nâng cao hiệu năng thi hành các truy vấn đồng thời (cả về khoảng cách ngắn nhất và cập nhật) trên đồ thị động cũng như cải thiện hiệu năng tính một số độ đo trung tâm phục vụ phân tích đồ thị có quy mô lớn. Mục tiêu này sẽ được thể hiện cụ thể thông qua các nội dung nghiên cứu chính trong luận án như sau: 1. Nghiên cứu, khảo sát và đánh giá một số phương pháp, kỹ thuật tổ chức dữ liệu đồ thị cũng như các phép toán cơ bản trên đồ thị.edu/ 14 https://bigdata.jp/wp/english/ 15 http://law.php Trang 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 1.
GIỚI THIỆU CHUNG 2. Nghiên cứu xây dựng mô hình đặc tả bài toán xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động, quy mô lớn. Đề xuất một số giải pháp để nâng cao hiệu năng thi hành các truy vấn khoảng cách ngắn nhất trên đồ thị động, quy mô lớn dựa trên cách tiếp cận tổ chức dữ liệu phù hợp và tính toán song song. Nâng cao hiệu năng một số giải thuật tính các độ đo phục vụ các phép toán phân tích đồ thị dựa trên cách tiếp cận tổ chức dữ liệu phù hợp và tính toán song song.
Tiến hành cài đặt thử nghiệm các giải pháp đã xây dựng trong luận án; đánh giá và so sánh với một số giải pháp hiện có dựa trên những bộ dữ liệu chuẩn.2 Phạm vi và phương pháp nghiên cứu Về phạm vi, trong luận án này chúng tôi chỉ chú trọng đến bài toán nghiên cứu trên đồ thị không trọng số. Đối với bài toán xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động, chúng tôi quan tâm đến đồ thị có hướng, không trọng số với các phép toán thêm cạnh, xoá cạnh (từ đó có thể hình thành các phép toán thêm/xoá đỉnh) và truy vấn khoảng cách ngắn nhất giữa hai đỉnh. Đối với các phép toán hỗ trợ phân tích đồ thị quy mô lớn, chẳng hạn như các mạng xã hội, một số độ đo trung tâm sẽ được quan tâm, đề xuất giải pháp nâng cao hiệu năng tính toán các độ đo này trong luận án. Với năng lực của hạ tầng tính toán tiếp cận được, hiện chúng tôi chưa thể tiến hành để giải quyết hiệu quả đối với đồ thị có quy mô quá lớn trên một tỷ đỉnh, chẳng hạn như dữ liệu mạng Facebook.
Về phương pháp nghiên cứu, trong luận án này chúng tôi sẽ kết hợp cả phương pháp nghiên cứu lý thuyết lẫn nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết, chúng tôi sẽ tiến hành thu thập các tài liệu khoa học đã được công bố tại các nhà xuất bản, trường Đại học có uy tín trong và ngoài nước để từ đó phân tích, đánh giá những phương pháp, kỹ thuật cũng như kết quả thu được trong lĩnh vực liên quan đến bài toán nghiên cứu của luận án. Các đề xuất trong luận án cũng được chú trọng phân tích, đánh giá tường minh về tính đúng đắn, độ phức tạp về mặt lý thuyết. Về nghiên cứu thực nghiệm, chúng tôi sẽ áp dụng phương pháp thực nghiệm đối với toàn bộ các giải pháp, đề xuất của chúng tôi để kiểm nghiệm lại kết quả lý thuyết.
Việc thực nghiệm cũng được tiến hành trên những bộ dữ liệu thường xuyên được cộng đồng nghiên cứu sử dụng và trên cùng nền tảng tính toán để có thể so sánh với những giải pháp khác đã được công bố.4 Các đóng góp chính của luận án Trong quá trình thực hiện luận án này, chúng tôi đã thu được những kết quả chính sau đây: Trang 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 1. GIỚI THIỆU CHUNG 1. Mô hình hoá quá trình xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động, quy mô lớn dựa vào lịch thi hành phép toán đồng thời và dựa vào cấu trúc dữ liệu phù hợp cho phép nâng cao hiệu năng bộ nhớ đệm cache. Đóng góp này được công bố trong công trình được đăng trên kỷ yếu hội thảo quốc tế ICCCI năm 2017 [DPH2].
Đề xuất ba giải pháp (akGroup, akGroupPlus và bigGraph) để nâng cao hiệu năng thi hành các truy vấn đồng thời trên đồ thị động quy mô lớn với khả năng thi hành song song cả các truy vấn duyệt đồ thị lẫn cập nhật đồ thị. Cả ba giải pháp này đều dựa trên ý tưởng chính là (i) xây dựng cấu trúc dữ liệu đồ thị phù hợp để nâng cao hiệu năng của bộ nhớ đệm cache; (ii) lựa chọn hướng duyệt đồ thị một cách linh hoạt dựa không chỉ vào số lượng đỉnh con mà cả số lượng đỉnh cháu của mỗi hàng đợi; và (iii) đề xuất giải pháp song song hoá các truy vấn đồng thời, cả đối với các phép toán cập nhật lẫn truy vấn khoảng cách ngắn nhất trên đồ thị. Các kết quả này đã được chúng tôi công bố trong công trình [DPH1] tại hội thảo BDCAT về quản lý dữ liệu lớn năm 2016, hội thảo quốc tế ICCCI năm 2017 [DPH2] và công bố trong tạp chí quốc tế Transactions on Computational Collective Intelligence, Springer, năm 2018 [DPH3]. Xây dựng hai giải thuật nâng cao hiệu năng quá trình tính độ trung tâm gần và độ trung tâm trung gian trên đồ thị quy mô lớn với giải pháp bigGraph được xây dựng dựa trên việc (i) tổ chức dữ liệu đồ thị phù hợp và (ii) song song hoá các phép tính SSSP trên mỗi đỉnh của đồ thị.
Kết quả này của chúng tôi đã được công bố trong kỷ yếu hội thảo quốc tế SoICT năm 2018 [DPH4].5 Tổ chức của luận án Ngoài phần mở đầu giới thiệu chung, bố cục của luận án được tổ chức thành 5 chương được minh hoạ như hình 1. Nội dung chính của các chương như sau: • Chương 1 giới thiệu chung về động lực nghiên cứu, mục tiêu và các nội dung chính của luận án. Ngoài ra, các nghiên cứu liên quan cũng như các đóng góp chính của luận án cũng được trình bày trong chương này. • Chương 2 có nhiệm vụ trình bày các kiến thức cơ sở liên quan đến những nội dung nghiên cứu của luận án.
Trong chương này, chúng tôi sẽ giới thiệu sơ lược về lý thuyết đồ thị, các phương pháp tổ chức dữ liệu đồ thị, các phép toán toán cơ bản trên đồ thị và một số những khái niệm cơ bản liên quan đến tính toán song song. • Chương 3 của luận án giới thiệu về mô hình hoá các truy vấn tính khoảng cách ngắn nhất trên đồ thị động, quy mô lớn, từ đó chú trọng, đi sâu trình bày ba giải pháp chính được xây dựng trong luận án để nâng cao hiệu năng xử lý các truy vấn đồng thời tính khoảng cách ngắn nhất và cập nhật đồ thị quy mô lớn. Các giải pháp này được chứng Trang 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƯƠNG 1. GIỚI THIỆU CHUNG Hình 1.1: Lược đồ tổ chức luận án minh tính đúng đắn, hiệu quả thông qua các thực nghiệm sử dụng những bộ dữ liệu được cộng đồng nghiên cứu thường sử dụng và đánh giá, so sánh với những công cụ tương tự.
• Chương 4 trình bày một số kết quả nghiên cứu về việc tính các độ đo trung tâm của đồ thị theo định hướng song song hoá kết hợp sử dụng cấu trúc dữ liệu đồ thị phù hợp. Hai giải pháp tính độ trung tâm gần và độ trung tâm trung gian đã được chúng tôi trình bày trong chương này. Các kết quả thực nghiệm minh chứng việc cải thiện hiệu năng của hai giải pháp đề xuất trong luận án thông qua đánh giá, so sánh với một số bộ công cụ tương tự cũng được tiến hành và trình bày cụ thể trong chương này. • Chương 5 tóm lược lại các đóng góp chính của luận án và một số hướng phát triển trong tương lai.
Trang 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2 CƠ SỞ LÝ THUYẾT Trong chương này, luận án sẽ chú trọng trình bày những khái niệm lý thuyết cơ bản liên quan đến luận án, cụ thể là lý thuyết đồ thị, các phương pháp biểu diễn đồ thị cũng như các phép toán cơ bản trên đồ thị. Một số những khái niệm cơ bản liên quan đến tính toán song song cũng sẽ được trình bày trong luận án này.1 Khái niệm Đồ thị là một cấu trúc dữ liệu linh hoạt, được thể hiện dưới dạng một tập các đỉnh (vertices) và các cạnh (edges), hay được gọi với thuật ngữ khác là tập các nút (nodes) và các quan hệ kết nối giữa chúng với nhau (relationships) [103][108]. Đồ thị cho phép biểu diễn các thực thể dưới dạng các đỉnh và các cách thức mà các thực thể đó liên quan đến nhau dưới dạng các mối quan hệ.