I. Giới thiệu
Luận án tiến sĩ của Xifeng Yan tập trung vào việc khai thác dữ liệu, lập chỉ mục, và tìm kiếm tương đồng trong tập dữ liệu đồ thị lớn. Nghiên cứu này nhấn mạnh sự cần thiết của các thuật toán phân tích có khả năng mở rộng để xử lý các đồ thị lớn, đặc biệt trong các lĩnh vực như sinh học tính toán và kỹ thuật phần mềm. Đồ thị được sử dụng rộng rãi để biểu diễn các cấu trúc phức tạp như protein, hợp chất hóa học, và luồng chương trình. Việc phân tích thủ công các đồ thị lớn là không khả thi, do đó, các công cụ tự động hóa là cần thiết.
1.1. Động lực nghiên cứu
Nghiên cứu này xuất phát từ nhu cầu thực tế trong việc phân tích đồ thị và tìm kiếm tương đồng trong các tập dữ liệu đồ thị lớn. Các ứng dụng như phân tích mạng protein, tìm kiếm hợp chất hóa học, và phân tích luồng chương trình đòi hỏi các giải pháp hiệu quả. Việc khai thác các mẫu đồ thị và xây dựng chỉ mục là hai vấn đề cốt lõi được đề cập trong luận án.
II. Khai thác mẫu đồ thị
Luận án đề xuất một hệ thống gán nhãn đồ thị, gSpan, để giải quyết vấn đề khai thác dữ liệu trong tập dữ liệu đồ thị lớn. gSpan loại bỏ sự cần thiết của các phép nối đồ thị, giúp giảm chi phí tính toán. Nghiên cứu cũng chỉ ra rằng việc khai thác các mẫu đồ thị thường xuyên là một bài toán NP-đầy đủ, đòi hỏi các giải pháp tối ưu hóa.
2.1. Phương pháp khai thác dựa trên Apriori
Phương pháp này dựa trên nguyên lý Apriori để khai thác các mẫu đồ thị thường xuyên. Tuy nhiên, nó tạo ra nhiều ứng viên không cần thiết, dẫn đến chi phí tính toán cao.
2.2. Phương pháp khai thác dựa trên tăng trưởng mẫu
Phương pháp này tập trung vào việc mở rộng các mẫu đồ thị hiện có thay vì tạo ra các ứng viên mới, giúp giảm chi phí tính toán và cải thiện hiệu suất.
III. Lập chỉ mục đồ thị
Luận án giới thiệu gIndex, một phương pháp lập chỉ mục hiệu quả cho tập dữ liệu đồ thị lớn. gIndex sử dụng các mẫu đồ thị thường xuyên và có tính phân biệt để xây dựng chỉ mục, giúp giảm kích thước chỉ mục và cải thiện tốc độ tìm kiếm. Phương pháp này vượt trội so với các phương pháp truyền thống về cả kích thước và hiệu suất.
3.1. Chọn lọc các đoạn đồ thị phân biệt
Phương pháp này tập trung vào việc chọn lọc các đoạn đồ thị có tính phân biệt cao để xây dựng chỉ mục, giúp giảm số lượng mục chỉ mục và cải thiện hiệu suất tìm kiếm.
3.2. Duy trì chỉ mục khi thêm xóa đồ thị
Luận án cũng đề xuất các phương pháp để duy trì chỉ mục khi có sự thay đổi trong tập dữ liệu đồ thị, đảm bảo tính nhất quán và hiệu suất của chỉ mục.
IV. Tìm kiếm tương đồng trong đồ thị
Luận án nghiên cứu các phương pháp tìm kiếm tương đồng trong tập dữ liệu đồ thị lớn, bao gồm tìm kiếm chính xác và tìm kiếm gần đúng. Các phương pháp này được áp dụng trong các lĩnh vực như sinh học tính toán và hóa học, giúp tăng tốc quá trình phân tích và khám phá tri thức.
4.1. Tìm kiếm tương đồng dựa trên cấu trúc con
Phương pháp này tập trung vào việc tìm kiếm các cấu trúc con tương đồng trong đồ thị, giúp xác định các mẫu đồ thị có ý nghĩa trong các ứng dụng thực tế.
4.2. Tìm kiếm tương đồng dựa trên khoảng cách chồng chéo
Phương pháp này sử dụng khoảng cách chồng chéo để đo lường sự tương đồng giữa các đồ thị, giúp cải thiện độ chính xác của kết quả tìm kiếm.
V. Ứng dụng thực tiễn
Luận án cung cấp các nghiên cứu chuyên sâu về phân tích đồ thị, phân loại dựa trên mẫu, và khai thác mẫu có ràng buộc. Các ứng dụng thực tiễn bao gồm phân tích mạng gene, phân tích luồng chương trình để tự động phát hiện lỗi phần mềm, và phân tích hợp chất hóa học trong nghiên cứu dược phẩm.
5.1. Phân tích mạng gene
Nghiên cứu này áp dụng các phương pháp khai thác đồ thị để phân tích mạng gene, giúp xác định các mạng con quan trọng trong các quá trình sinh học.
5.2. Phân tích luồng chương trình
Luận án đề xuất các phương pháp phân tích luồng chương trình để tự động phát hiện lỗi phần mềm, giúp cải thiện chất lượng phần mềm.
