Luận Án Tiến Sĩ: Phương Pháp Khai Thác, Lập Chỉ Mục và Tìm Kiếm Tương Đồng Trong Tập Dữ Liệu Đồ Thị Lớn

• Tác giả: Xifeng Yan
• Trường học: University of Illinois at Urbana-Champaign
• Chuyên ngành: Computer Science
• Đề tài: Mining, Indexing and Similarity Search in Large Graph Data Sets
• Loại tài liệu: thesis
• Năm xuất bản: 2006
• Địa điểm: Urbana

• CERTIFICATE OF COMMITTEE APPROVAL
• Abstract
• Acknowledgments
• Table of Contents
• 1. CHƯƠNG 1: INTRODUCTION
• 1.1. Motivation
• 2. CHƯƠNG 2: GRAPH PATTERN MINING
• 2.1. Apriori-based Mining
• 2.2. Pattern Growth-based Mining
• 2.3. Right-Most Extension
• 2.4. DFS Lexicographic Order
• 2.5. Closed Graph Pattern
• 2.6. Failure of Early Termination
• 2.7. Detecting the Failure of Early Termination
• 2.8. Variant Graph Patterns
• 2.8.1. Contrast Graph Pattern
• 2.8.2. Coherent Graph Pattern
• 2.8.3. Discriminative Graph Pattern
• 2.8.4. Dense Graph Pattern
• 2.8.5. Approximate Graph Pattern
• 2.9. Relevance-Aware Top-K
• 2.10. Pattern-Based Classification
• 2.11. Automated Software Bug Isolation
• 2.11.1. Uncover “Backtrace” for Noncrashing Bugs
• 2.12. Graph Patterns with Constraints
• 2.12.1. Highly Connected Graph Patterns
• 2.12.2. CloseCut: A Pattern Growth Approach
• 2.12.3. SPLAT: A Pattern Reduction Approach
• 2.12.4. Pruning Patterns
• 2.12.5. Gene Relevance Network Analysis
• 3. CHƯƠNG 3: GRAPH INDEXING
• 3.1. Graph Query Processing
• 3.2. Path-based Graph Indexing
• 3.3. Discriminative Fragment Selection
• 3.4. Insert/Delete Maintenance
• 4. CHƯƠNG 4: GRAPH SIMILARITY SEARCH
• 4.1. Substructure Similarity Search
• 4.2. Feature-Graph Matrix
• 4.3. Feature Miss Estimation
• 4.4. Feature Set Selection
• 4.4.1. Complexity of Optimal Feature Set Selection
• 4.4.2. Clustering based Feature Set Selection
• 4.5. Substructure Search with Superimposed Distance
• 4.6. Framework of Partition-Based Index and Search
• 4.7. Fragment-based Index
• 4.8. Partition-based Search
• List of Figures
• List of Tables
• Glossary of Notation

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.