Bài giảng Kho dữ liệu và kinh doanh thông minh - Bài 5: Lập chỉ mục

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

2
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kho dữ liệu và kinh doanh thông minh - Bài 5: Lập chỉ mục, trình bày các nội dung chính như sau: Chỉ mục dựa trên cây; Chỉ mục bitmap. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kho dữ liệu và kinh doanh thông minh - Bài 5: Lập chỉ mục

KHO DỮ LIỆU VÀ KINH DOANH THÔNG MINH Bài 5: Lập chỉ mục
Nội dung  Chỉ mục dựa trên cây  Chỉ mục bitmap 2
Chỉ mục • Tại sao phải lập index? – Xem xét một bảng dữ liệu 100 GB; với tốc độ đọc 100 MB/s, cần 17 phút để quét qua toàn bảng – Câu truy vấn về số lượng máy S500 bán được ở Đức tháng trước • Áp dụng ràng buộc (sản phẩm, vị trí) khối lượng phải chọn sẽ giảm mạnh – Nếu bảng có 30 vị trí, 10000 sản phẩm và 24 tháng, khối lượng lựa chọn là 1/30 * 1/ 10000 * 1/24 = 0,00000014 – Như vậy chúng ta đọc 100 GB để lấy ra 1,4KB 3
Chỉ mục • Giảm số lượng các khối (trang/page) phải đọc với chỉ mục 4
Chỉ mục dựa trên Tree • B-Tree – Cấu trúc dữ liệu để lưu trữ dữ liệu được sắp xếp – Cấu trúc gồm các node 5
Cấu trúc cây • Tìm kiếm trong các hệ CSDL – B-Tree cho phép tìm kiếm với chi phí cỡ logarith 6
Cây cấu trúc • Tìm kiếm trong DW – Dữ liệu là đa chiều, tuy nhiên B-Tree chỉ hỗ trợ tìm kiếm 1 chiều – Liệu có thể mở rộng chức năng của cây để hỗ trợ dữ liệu đa chiều? 7
Cấu trúc cây • Ý tưởng cơ bản của các cây đa chiều – Mô tả tập điểm theo vùng hình học, chứa bó cụm của các điểm dữ liệu – Khi tìm kiếm, chỉ một số cụm được quan tâm chứ không phải mọi điểm – Các cụm/Cluster có thể chứa nhau, dẫn đến cấu trúc phân cấp 8
Cấu trúc cây • Các tiêu chuẩn khác nhau cho các cấu trúc cây – Cấu trúc phân cụm • Phân mảnh toàn không gian • Chỉ nhóm dữ liệu địa phương – Sự chồng xếp các cụm • Các cụm giao nhau • Các cụm tách biệt nhau – Sự cân bằng • Cân bằng • Không cân bằng 9
Cấu trúc cây • Lưu trữ đối tượng – Các đối tượng có thể ở lá hay node trong – Các đối tượng chỉ ở lá • Dạng hình học – Hình học cầu – Hình học khối 10
R-Tree • R-Tree (Guttman, 1984) là một mở rộng đa chiều của B-Tree – Thường sử dụng cho các ứng dụng có số chiều thấp (khoảng 10 chiều), như các hệ thống thông tin địa lý • Phiên bản mở rộng hơn: R+-Tree, R*-Tree, X-Tree – Lên tới hơn 20 chiều đối với các dữ liệu phân phối đều 11
Cấu trúc R-Tree • Cấu trúc chỉ mục động (có thể insert, update và delete) • Cấu trúc dữ liệu – Các trang dữ liệu/data page là các node lá và lưu các dữ liệu điểm cụm/cluster points và dữ liệu đối tượng – Các trang thư mục/directory page là các node trong và lưu các thực thể thư mục – Dữ liệu đa chiều được cấu trúc sử dụng MBR (hình chữ nhật bao tối thiểu/Minimum Bounding Rectangle) 12
Thí dụ R-Tree 13
Các tính chất của R-Tree • Lập các nhóm địa phương là các cụm • Các cụm có thể chồng nhau – Mức chồng nhau càng cao, hiệu quả của index càng thấp • Cấu trúc cây có chiều cao cân bằng – Tất cả các con của 1 node có cùng số lượng con cháu • Các đối tượng chỉ được lưu ở node lá – Node trong dùng để di chuyển trong cây • MBR thể hiện hình học 14
Các thuộc tính của R-Tree • Root có ít nhất 2 con • Mỗi nút trong có giữa m và M con • M và là các tham số xác định trước • Tất cả các lá của cây ở cùng 1 mức • Tất cả các lá có giữa m và M bản ghi chỉ mục • Các node trong: (I, child-pointer) với I là hình chữ nhật bao nhỏ nhất mà chứa hình chữ nhật của các node con • Các node lá: (I, tuple-id) với I là hình chữ nhật bao nhỏ nhất chứa các đối tượng dữ liệu (với ID tuple-id) 15
Các phép toán trên R-Tree • Các phép toán cơ bản để sử dụng và quản lý R-Tree gồm: – Search – Insert – Update – Delete – Splitting 16
Tìm kiếm trong R-Tree • Cây được tìm kiếm đệ quy từ root tới lá – 1 path được chọn – Nếu bản ghi không được tìm thấy, nhánh tiếp theo sẽ được tìm • Lựa chọn path tùy ý 17
Thí dụ • Kiểm tra chỉ 7 node thay vì 12 18
Tìm kiếm trong R-Tree • Không đảm bảo hiệu năng tốt • Trong trường hợp tồi nhất phải tìm tất cả các path (do sự chồng nhau của các MBR) • Thuật toán tìm kiếm cố gắng loại bỏ các vùng không liên quan càng nhiều càng tốt (“tỉa”) 19
Thuật toán tìm kiếm • Tất cả các thực thể chỉ mục giao với hình chữ nhật tìm kiếm được duyệt – Tìm kiếm trên các node trong • Kiểm tra sự giao cắt của các MBR với truy vấn • Với các MBR giao cắt, tìm kiếm trên tất cả các con của nó – Tìm kiếm trên các node lá • Kiểm tra tất cả các điểm dữ liệu để xác định xem nó có giao với truy vấn không • Tìm kiếm đối trượng chính xác trong tập kết quả 20