Bài giảng Tìm kiếm và trình diễn thông tin - Bài 18: Vấn đề tìm kiếm trên Web - Nguyễn Bá Ngọc

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Bài 18: Vấn đề tìm kiếm trên Web - Nguyễn Bá Ngọc

1. (IT4853) Tìm kiếm và trình diễn thông tin Vấn đề tìm kiếm trên Web
2. Giảng viên  TS. Nguyễn Bá Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: 2
3. Nội dung chính  Đặc điểm Web  Ước lượng kích thước  Căn bản tìm kiếm trên Web 3
4. Khó khăn với tìm kiếm trên Web Web toàn cầu:  Phân tán;  Thay đổi thường xuyên;  Rất lớn;  Phi cấu trúc;  Nhiều trùng lặp;  Chất lượng không đồng nhất;  Đa ngôn ngữ. 4
5. Sao lưu Web   Thu gom bởi Alexa và Compaq  Năm 2001 quy mô 4 tỉ trang (40 TB)  Năm 2002: 100TB  Được ví như “cỗ máy thời gian” với khả năng hiển thị trang web như trong quá khứ 5
6. Đặc điểm đồ thị Web  Coi mỗi trang web (được xác định bởi một url duy nhất) là một đỉnh của độ thị, các siêu liên kết là các cạnh có hướng của đồ thị.  Broder et al (2000), WWW9  Công trình nghiên cứu tính chất đồ thị web quy mô lớn  Dữ liệu được thu thập hai lần từ AltaVista  Tháng 5 năm 99: 203M trang, 1.5 tỉ liên kết;  Tháng 10 năm 99: 271M trang, 2.1 tỉ liên kết. 6
7. Những thuộc tính đồ thị cơ bản  Bậc-vào của một đỉnh là số cạnh đi tới một nút  Bậc-ra: số cạnh đi ra từ một nút  Đường kính  Giá trị cực đại của các độ dài ngắn nhất giữa tất cả cặp đỉnh (u, v).  Thành phần liên kết  Thành phần liên kết yếu (WCC – Weakly connected component) là tập đỉnh trong đồ thị vô hướng, trong đó luôn tồn tại đường đi giữa hai nút bất kỳ;  Thành phần liên kết mạnh (SCC – Strongly connected component) là thành phần liên kết trong đồ thị có hướng. 7
8. Kết quả nghiên cứu  Broder et al (2000), WWW9 2.1  Số lượng trang với bậc vào i ∝ 1/i  Thống nhất với những nghiên cứu trên quy mô nhỏ hơn  Kích thước của thành phần liên kết cũng tuân theo quy luật lũy thừa  WCC lớn nhất 91%, SCC lớn nhất 26% 8
9. Kết cấu web, hình nơ 9
10. Đường dẫn và tính liên thông  Đường kính tối thiểu của SCC là 28  Đường kính của toàn bộ Web là trên 500  Không phải tất cả cặp đỉnh đều liên thông  Cho cặp (u, v) ngẫu nhiên, P(path(u, v))=0,24  Xác suất tồn tại đường đi từ u đến v là 0,24  Độ dài trung bình của đường dẫn có hướng là 16  Đường dẫn vô hướng là 6  Tuy nhiên trong trường hợp tổng quát, Web có mức liên thông cao  Nếu loại bỏ đỉnh với bậc vào > 5, trên Web vẫn tồn tại thành phần liên thông yếu ~ 59M nút 10
11. Nội dung chính  Đặc điểm Web  Ước lượng kích thước  Căn bản tìm kiếm trên Web 11
12. Web lớn tới mức nào  Kích thước web là vô hạn  Nội dung động  Soft 404: www.yahoo.com/  Web tĩnh chứa nhiều trùng lặp (~30%) 12
13. Kích thước chỉ mục tìm kiếm  Công cụ tìm kiếm đánh chỉ mục web tĩnh  Các công cụ tìm kiếm khác nhau có chỉ mục khác nhau:  Độ sâu url, luật phát hiện spam, độ ưu tiên v.v.  thu thập các nội dung khác nhau từ một URL 13
14. Sec. 19.5 Tỉ lể chỉ mục Lấy mẫu ngẫu nhiên URLs từ A, kiểm tra nếu có trong B; và ngược lại A B A  B = (1/2) * Size A A  B = (1/6) * Size B (1/2)*Size A = (1/6)*Size B \ Size A / Size B = (1/6)/(1/2) = 1/3 Phép thử: (i) Lấy mẫu (ii) Kiểm tra 14
15. Sec. 19.5 Các truy vấn trong nghiên cứu của Lawrence và Giles  adaptive access control  softmax activation function  neighborhood preservation  bose multidimensional system topographic theory  hamiltonian structures  gamma mlp  right linear grammar  dvi2pdf  pulse width modulation neural  john oliensis  unbalanced prior probabilities  rieke spikes exploring neural  ranked assignment method  video watermarking  internet explorer favourites  counterpropagation network importing  fat shattering dimension  karvel thornber  abelson amorphous computing  zili liu 15
16. Ước lượng kích thước của Web [Lawr98, Bhar98a]  Giả sử các công cụ tìm kiếm đánh chỉ mục một tập con ngẫu nhiên của Web Nếu E2 chứa x% của E1, thì E2 cũng chứa x% của Web E2 E1 Biết kích thước E2 Kích thước Web = 100*E2/x WEB Bharat & Broder: 200 M (Nov 97), 275 M (Mar 98) Lawrence & Giles: 320 M (Dec 97)
17. Lấy mẫu URLs  Lý tưởng: Sinh ngẫu nhiên URL và kiểm tra tồn tại trong chỉ mục.  Vấn đề: Khó xây dựng giải thuật sinh ngẫu nhiên URL! Có thể sinh ngẫu nhiên URL có trong chỉ mục của công cụ tìm kiếm.  Giải pháp 1: Sinh ngẫu nhiên URL trong chỉ mục của công cụ tìm kiếm.  Xác định tỉ lệ chỉ mục  Giải pháp 2: Random walks / địa chỉ IP  Trên lý thuyết có thể xác định kích thước Web. 17
18. Tỉ lệ đánh chỉ mục Web  Lawrence and Giles (1998) xác định cận dưới đối với Web: 320M trang có thể đánh chỉ mục.  Công cụ tìm kiếm chỉ phủ một phần nhỏ của Web:  HotBot phủ 34%,  AltaVista, 28%  Northern Light, 20%  Excite, 14%  Infoseek, 10%  Lycos, 3% 18
19. Nội dung chính  Đặc điểm của Web  Ước lượng kích thước  Căn bản tìm kiếm trên Web 19
20. Tìm kiếm là hoạt động thường xuyên nhất trên Web 20
21. Tổng quan công cụ tìm kiếm trên Web 21
22. Vai trò của công cụ tìm kiếm web  Là động lực thúc đẩy người dùng công bố nội dung trên web  Có nên công bố thông tin nếu không ai đọc nó?  Có nên công bố nội dung nếu không thu được lợi nhuận?  Tìm kiếm giải quyết vấn đề kinh phí vận hành web  Máy chủ, thiết bị mạng, việc biên soạn nội dung v.v.  Ngày nay phần lớn chi phí được trả nhờ quảng cáo trong tìm kiếm; 22
23. Nhu cầu thông tin  Need [Brod02, RL04]  Thông tin (Informational): Học về một vấn đề nào đó (~40%/65%)  Định vị (Navigational): Địa chỉ một trang cụ thể (~25%/15%)  Giao dịch (transactional): Dịch vụ, tải dữ liệu, mua sắm, v.v., (~35%)  Trung gian (Gray areas) 23
24. Phạm vi tìm kiếm kết quả (Source: iprospect.com WhitePaper_2006_SearchEngineUserBehavior.pdf) 24