Luận án TS: Nâng cao hiệu năng thi hành các phép toán trên đồ thị

1. Mở đầu

1.1 Mục tiêu nghiên cứu

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ị.

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. 

1.2 Phạm vi nghiên cứu

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.

1.3 Phương pháp nghiên cứu

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ố.

2. Nội dung

3. Kết luận

Thực tế đã chứng minh được tính hiệu quả của lý thuyết đồ thị trong những bài toán thực tiễn, chẳng hạn như mô hình hoá các phép toán trên mạng xã hội Facebook, Twitter... Luận án này quan tâm đến việc ứng dụng lý thuyết đó để giải quyết bài toán quan trọng: nâng cao hiệu năng xử lý các phép toán đồng thời trên đồ thị. Với định hướng đó, chúng tôi đã tiến hành xác lập mục tiêu và các nội dung nghiên cứu chính của luận án (đã trình bày ở Chương 1). Qua các kết quả cả về lý thuyết lẫn thực nghiệm đã được trình bày cụ thể trong luận án, có thể khẳng định rằng toàn bộ mục tiêu và các nội dung nghiên cứu đề ra đã được hoàn thành, với các đóng góp chính bao gồm:

• Mô hình hoá quá trình xử lý các phép toán tương tranh trên đồ thị quy mô lớn dựa vào lịch thi hành các phép toán đồng thời và dựa vào cấu trúc dữ liệu phù hợp; từ đó cho phép nâng cao hiệu năng bộ nhớ đệm cache và giảm thời gian truy xuất đến bộ nhớ chính.
• Đề 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ị.
• Nâng cao hiệu năng quá trình tính hai độ đo trung tâm: độ 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 tổ chức dữ liệu đồ thị phù hợp và song song hoá các phép tính SSSP trên mỗi thành viên của mạng.

4. Tài liệu tham khảo

S. Adve, V. Adve, G. Agha, M. I Frank María, M. Garzarán, J. Hart, W.-m. Hwu, R. Johnson, K. Rakesh Kumar, D. Marinov, K. Nahrstedt, D. Padua, M. Parthasarathy, S. Patel Grigore Rosu, D. Roth, M. Snir, J. Torrellas, and C. Zilles. Parallel computing research at illinois the upcrc agenda. November 2008.

R. Alhajj and J. Rokne. Encyclopedia of Social Network Analysis and Mining. Springer, 1st edition, 2014. ISBN 978-1-4614-6169-2.

G. S. Almasi and A. Gottlieb. Highly Parallel Computing. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, USA, 1989. ISBN 0-8053-0177-1.

K. Asanovic, R. Bodik, B. Catanzaro, J. James Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. Plishker, J. Shalf, S. Williams, and K. Yelick. The landscape of parallel computing research: A view from berkeley. EECS Department, University of California, Berkeley, EECS-2006-183:56, 12 2006....