Mining, indexing and similarity search in large graph data sets
Luận án · Tiến sĩ · năm 2006 · đề tài tham khảo
| Loại tài liệu | Luận án |
|---|---|
| Bậc học | Tiến sĩ |
| Ngành | Công nghệ thông tin |
| Tác giả | Xifeng Yan |
| Cơ sở đào tạo | Đại học Quốc gia TP. Hồ Chí Minh |
| Năm | 2006 |
| Nguồn | Thư viện số Đại học Quốc gia TP. Hồ Chí Minh · trang gốc |
Tóm tắt
Scalable analytical algorithms and tools for large graph data sets are in great demand across domains from software engineering to computational biology as it is very difficult, if not impossible, for human beings to manually analyze any reasonably large collection of graphs due to their high complexity. In this dissertation, we investigate two long standing fundamental problems: Given a graph data set, what are the hidden structural patterns and how can we find them? and how can we index graphs and perform similarity search in large graph data sets? Graph pattern mining is an expensive computational problem since subgraph isomorphism is NP-complete. Previous solutions generate inevitable overheads since they rely on joining two graphs to form larger candidates. We develop a graph canonical labeling system, gSpan, showing both theoretically and empirically that this kind of join operation is unnecessary. Graph indexing, the second problem addressed in this dissertation, may incur an exponential number of index entries if all of the substructures in a graph database are used for indexing. The solution, gindex, proposes a novel, frequent and discriminative graph mining approach that leads to the development of a compact but effective graph index structure that is orders of magnitude smaller in size but an order of magnitude faster in performance than traditional approaches. Besides graph mining and search, this dissertation provides thorough investigation of pat-tern summarization, pattern-based classification, constraint pattern mining, and graph similarity searching, which could leverage the usage of graph patterns. It also explores several critical applications in bioinformatics, computer systems and software engineering, including gene relevance network analysis for functional annotation, and program flow analysis for automated software bug isolation. The developed concepts, theories, and systems may significantly deepen the understanding of data mining principles in structural pattern discovery, interpretation and search. The for¬mulation of a general graph information system through this study could provide fundamental supports to graph-intensive applications in multiple domains.
Bản toàn văn lưu tại thư viện Đại học Quốc gia TP. Hồ Chí Minh
Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.
Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
- Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
- Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
- Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.
Hướng dẫn chọn đề tài, cấu trúc và số liệu cho ngành này: Luận văn công nghệ thông tin · Hỏi đáp từng chương với người hướng dẫn số: Học Giả Số · Công cụ số: Luận Văn Số.
Đề tài cùng ngành
- Designing intelligent tutors that adapt to when students game the system
- Phát triển hệ thống chuyển đổi ngôn ngữ ký hiệu sang ngôn ngữ tự nhiên
- Ứng dụng giải thuật di truyền đa mục tiêu trong việc thiết kế chi tiết máy
- Building a cloud based quiz system for student studying
- Building a blood donation application
- Nghiên cứu và ứng dụng thuật toán học máy để cải thiện chất lượng mô hình côn trùng 3D
- Một phương pháp chuyển đổi cơ sở dữ liệu quan hệ sang cơ sở dữ liệu hướng đối tượng
- Xây dựng hệ thống truy vấn ảnh dựa vào văn bản ngoại cảnh
Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.