Chuyên Đề Giới thiệu về máy tìm kiếm ASPseek và đề xuất giải pháp song song hóa

Mục lục
Mục lục . 1
Chương 1. Tổng quan về khai phá dữ liệu Web và máy tìm kiếm 4
1.1. Khai phá dữ liệu Web 4
1.1.1. Tổng quan về khai phá dữ liệu Web 4
1.1.2 Các bài toán được đặt ra trong khai phá Web . 5
1.1.3 Các lĩnh vực của khai phá dữ liệu Web . 6
1.1.3.1 Khai phá nội dung Web (Web content mining): . 6
1.1.3.2. Khai phá cấu trúc web (web structure mining): 6
1.1.3.3 Khai phá sử dụng web (web usage mining). 7
1.1.4. Khó khăn 7
1.1.4.1 Web dường như quá lớn để tổ chức thành kho dữ liệu phục vụ Dataming 7
1.1.4.2. Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản
truyền thống khác 8
1.1.4.3. Web là một nguồn tài nguyên thông tin có độ thay đổi cao 8
1.1.4.4. Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng 8
1.1.4.5. Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích . 9
1.1.5. Thuận lợi 9
1.2 Tổng quan về máy tìm kiếm 9
1.2.1 Nhu cầu: 9
1.2.2 Cơ chế hoạt động của máy tìm kiếm. 10
1.2.3 Cấu trúc điển hình của một máy tìm kiếm 11
Chương 3. Tổng quan về xử lý song song 34
3.1 Máy tính song song 34
3.1.2 Phân loại máy tính song song 35
3.1.2.1 Phân loại dựa trên cơ chế điều khiển chung 35
3.1.2.2 Cách phân loại dựa trên sự tương tác giữa các BXL . 37
3.2 Mô hình lập trình song song . 38
3.2.1 Mô hình nhiệm vụ - kênh liên lạc 38
3.2.1.1 Đặc điểm mô hình nhiệm vụ-kênh liên lạc . 38
3.2.1.2 Đặc điểm của mô hình nhiệm vụ - kênh liên lạc. 39
3.2.2 Mô hình chia sẻ bộ nhớ chung 40
3.3. Hiệu năng của xử lý song song . 40
3.3.1 Khả năng tăng tốc độ tính toán: 40
3.3.3 Cân bằng tải 43
3.3.4 Sự bế tắc 44




3.4 Môi trường lập trình song song 45
3.4.1 Mô hình MPI (Message Passing Interface) 46
3.4.2 PVM (Parallel Virtual Machine) 46
3.4.3 So sánh giữa MPI và PVM. 46
3.5 Giao thức truyền thông điệp MPI 47
Chương 2: Giới thiệu về module Crawler trong các máy tìm kiếm 13
2.1 Tổng quan: . 13
2.2 Cấu trúc cơ bản của một crawler 15
2.2.1 Frontier 16
2.2.2 History và kho chứa trang web . 17
2.2.3 Tải các trang web (fetching) 18
2.2.4 Duyệt nội dung (parsing) . 19
2.2.4.1. Quá trình lấy ra và chuẩn hóa các URL 20
2.2.4.2 Loại bỏ các từ dừng và chuyển các dạng thức của từ sang dạng gốc 21
2.2.4.3 Xây dựng cây các thẻ HTML 21
2.3 Các crawler đa luồng (Multi-threaded crawlers) 22
2.4. Các thuật toán crawling . 24
2.4.1 Thuật toán Naïve tốt nhất đầu tiên 24
2.4.2 Thuật toán SharkSearch 25
2.4.3 Crawler có trọng tâm (focused crawler) 26
2.3.4 Các crawler tập trung theo ngữ cảnh (context focused crawler). 27
2.4. Các tiêu chuẩn đánh giá các crawler 29
2.4.1 Độ quan trọng của trang web 29
2.4.2 Các phân tích tổng hợp 31
Chương 4. Giới thiệu về máy tìm kiếm ASPseek và đề xuất giải pháp song
song hóa 50
4.1 Giới thiệu chung về máy tìm kiếm ASPseek 50
4.1.1 Một số tính năng của ASPseek . 50
4.1.2 Các thành phần của ASPseek . 51
a. Module đánh chỉ số (indexing) 51
b. Module tìm kiếm (searchd) 52
c. Module tìm kiếm s.cgi. 52
4.2 Cấu trúc cơ sở dữ liệu trong máy tìm kiếm ASPseek . 52
4.2.1 Cấu trúc một số bảng chính trong cơ sở dữ liệu của ASPseek . 53
4.2.2 Cấu trúc một số file nhị phân trong cơ sở dữ liệu của ASPseek . 56
4.2.2.1 Cấu trúc các file nhị phân trong thư mục xxw: 56
4.3 Tìm hiểu về việc thực thi quá trình crawler trong module index của máy tìm
kiếm VietSeek. 60




4.3.1Quá trình crawler trong ASPseek. 60
4.3.2 Đề xuất giải pháp song song hóa . 63
4.3.2.1 Giải pháp song song hóa 63
4.3.2.2 Cơ chế phân công công việc giữa các bộ xử lý 65
4.3.2.3 Tổng hợp kết quả sau quá trình song song: 65
4.3.2.4 Vấn đề tương tranh giữa các bộ xử lý: . 66
4.3.2.5 Đánh giá giải pháp song song hóa 66
4.3.3.
Tài liệu tham khảo: . 68
Phụ lục: Một số hàm bổ sung trong Môđun indexing song song hóa