Luận văn "Tối ưu hóa truy vấn tìm đường ngắn nhất trên đồ thị động quy mô lớn" trình bày giải pháp để cải thiện hiệu năng quá trình tối ưu truy vấn trên đồ thị động, quy mô lớn có hướng, không trọng số, phương pháp tối ưu dựa trên các ý tưởng: cấu trúc dữ liệu phù hợp, tối ưu không gian tìm kiếm và cài đặt phù hợp. | ĐẠ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 Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 TÓM TẮT LUẬN VĂN THẠC SĨ NGÀNH HỆ THỐNG THÔNG TIN Hà Nội – 2016 Giới thiệu chung Động lực nghiên cứu Hiện nay, chúng ta đang sống trong thời đại bùng nổ về công nghệ công tin cũng như bùng nổ về các mạng xã hội. Một số mạng điển hình như 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 dữ liệu tăng nhanh chóng mặt. Để giải quyết những thách thức về mặt dữ liệu lớn trên, có rất nhiều phương pháp tiếp cận, trong đó phương pháp tiếp cận dựa trên đồ thị được cho là trực quan và phù hợp nhất [8]. Với việc sử dụng lý thuyết đồ thị, với các đỉnh biểu diễn các thực thể và các cạnh biểu diễn mối liên hệ giữa chúng. Trong đồ thị, tìm đường đi (ngắn nhất) là vấn đề tìm sự kết nối giữa hai đỉnh của một đồ thị và đảm bảo đường đi đó là ngắn nhất dựa trên một số yêu cầu cho trước. Đây là vấn đề nền tảng và cơ bản được áp dụng trong rất nhiều ứng dụng thực tế như tìm đường đi ngắn nhất giữa hai địa điểm sử dụng GPS hay tìm mối liên kết giữa hai người trên mạng xã hội [6]. Vấn đề này bình thường rất đơn giản, nhưng trong bối cảnh số lượng các đỉnh, cạnh của đồ thị rất lớn (vài triệu đỉnh) và thay đổi nhanh (thêm cạnh, bớt cạnh), làm thế nào để tối ưu hóa quá trình tìm đường đi ngắn nhất là một thách thức lớn [21]. Mục tiêu và nội dung chính của luận văn Với mục tiêu trên, luận văn này sẽ trình bày giải pháp để cải thiện hiệu năng quá trình tối ưu truy vấn trên đồ thị động, quy mô lớn có hướng, không trọng số. Phương pháp tối ưu dựa trên các ý tưởng: cấu trúc dữ liệu phù hợp, tối ưu không gian tìm kiếm và cài đặt phù hợp. Tổ chức luận văn Nội dung của luận văn sẽ được tổ chức như sau: Mở đầu: Đặt vấn đề Chương 1: Giới thiệu về cơ sở lý thuyết, các vấn đề liên quan đến đồ thị và bài toán tìm đường đi .
