Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 3: Các cấu trúc dữ liệu đa chiều - Nguyễn Thị Oanh

Nội dung text: Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 3: Các cấu trúc dữ liệu đa chiều - Nguyễn Thị Oanh

1. Plan  Lưu DL dạng điểm – k-D trees – Point Quadtrees – MX-Quadtrees  Lưu DL dạng vùng (chữ nhật): – R-trees 2
2. k-D trees  Dành lưu trữ dữ liệu điểm đa chiều (k-dimension) – 2-tree: lưu DL điểm 2 chiều – 3-tree: lưu DL điểm 3 chiều – – Mỗi điểm là vector có k phần tử  Không lưu DL vùng 4
3. VD: 2-D trees 6
4. 2-D trees  Cấu trúc 1 nút: INFO XVAL YVAL LLINK RLINK  Định nghĩa: 2-d tree là cây nhị phân thỏa mãn: – Nếu nút N ở mức chẵn : M N.LLINK : M.XVAL N.XVAL & P N.RLINK : P.XVAL N.XVAL – Nếu nút N ở mức lẻ: M N.LLINK : M.YVAL N.YVAL & 8 P N.RLINK : P.YVAL N.YVAL
5. Insertion/ Search in 2-D trees  Nút cần thêm: P(info, x, y)  Lặp: – Nút đang duyệt: N – Nếu N.XVAL = x và N.YVAL = y thì ghi đè N và kết thúc – Nếu N ở mức chẵn (0, 2, 4, ):  Nếu x < N.XVAL thì duyệt cây bên trái,  nếu không duyệt cây con bên phải – Nếu N ở mức lẻ (1, 3, 5, ):  Nếu y < N.YVAL thì duyệt cây bên trái,  nếu không duyệt cây con bên phải 10
6. Tìm nút thay thế cho nút bị xóa ?  Nếu xóa N tìm nút thay thế R: mọi nút thuộc cây con trái (N.LLINK) / phải của N cũng thuộc cây con trái (R.LLINK) / phải tương ứng của R: – Nếu nút N ở mức chẵn : M N.LLINK : M.XVAL R.XVAL & P N.RLINK : P.XVAL R.XVAL – Nếu nút N ở mức lẻ: M N.LLINK : M.YVAL R.YVAL & P N.RLINK : P.YVAL R.YVAL 12
7. Truy vấn phạm vi trên 2-D trees  Truy vấn phạm vi (range query): 1 điểm (xc, yc) + 1 khoảng cách r  Tìm các điểm (x,y) trên cây 2-D sao cho khoảng cách từ đó đến (xc, yc) <= r – L1: xc r x xc r yc r y yc r – L2 (Euclide) – 14
8. k-D trees: Lưu ý  Cây không cân bằng  Tùy thuộc vào thứ tự dữ liệu được insert vào  Một số biến thể: – k-D-B-tree: k-D tree + cây cân bằng (B-tree) – LSD-tree (Local Split Decision tree): đánh chỉ mục 2 mức: main memory + disk – VA-file (Vector Approximation file) 16
9. Cây tứ phân dạng điểm  Mỗi điểm trong cây sẽ chia 1 vùng thành 4 vùng con theo cả 2 chiều ngang và dọc (N.XVAL & N.YVAL): – NW (Northwest) – SW (Southwest) – NE (Northeast) – SE (Southeast) NW NE YVAL SW SE 18 XVAL
10. Thêm DL vào cây tứ phân  Banja Luka (19, 45)  Derventa (40, 50) Toslic  Toslic (38, 38) Tuzla  Tuzla (54, 40)  Sinji (4,4) 20
11. Xóa DL trong cây tứ phân  Nút lá: đơn giản – Thiết lập lại con trỏ ở nút cha = NULL và giải phóng nút cần xóa  Nút trong: phức tạp – Cần tìm nút thay thế ????? – VD: Xóa nút gốc trong ví dụ trên ? 22
12. Xóa DL trong cây tứ phân ( )  Xóa nút trong tìm nút thay thế chèn lại các nút trỏ bởi NW, SW, NE, SE Trường hợp tồi nhất: tất cả các nút bị thay đổi!!!!! 24
13. 3. MX-Quadtrees 26
14. MX-Quadtrees  Dữ liệu được chia theo lưới 2k x 2k  k tự chọn, nhưng sau khi chọn thì k phải không được thay đổi  Cấu trúc nút: – Tương tự cây tứ phân dạng điểm – Thông tin về vùng biểu diễn (XLB, XUB, YLB, YUB) – Nút gốc (root) : XLB = 0, XUB = 2k, YLB = 0, YUB = 2k 28
15. MX-Quadtree: Insert NW SW NE SE A (30, 50) root 60 nil nil nil nil nil nil 0,0 80 A (30,50) nil nil nil nil 30
16. MX-Quadtree: Insert NW SW NE SE A (30, 50) B (70, 55) root 60 nil nil nil nil nil nil nil nil nil nil 0,0 80 A (30,50) B(70,55) C (65, 25) nil nil nil nil nil nil nil nil C(65,25) nil nil nil nil 32
17. MX-Quadtree: Nhận xét  Tất cả các điểm được biểu diễn bởi nút lá  Nếu N là nút trong của cây MX-quadtree, thì vùng biểu diễn bởi N chứa ít nhất 1 điểm dữ liệu Xóa dễ dàng (Độ phức tạp: O(k)) 34
18. MX-Quadtree: Truy vấn phạm vi  Tương tự cây tứ phân dạng điểm  Điểm khác biệt: – Kiểm tra 1 điểm có nằm trong phạm vi truy vấn hay không chỉ thực hiện ở mức lá 36
19. 4. R-trees 38
20. G2 R7 R6 R5 R1 R4 G3 R2 R3 R8 G1 R9 R-tree bậc 4 42
21. R-trees: Insert G2 R7 R6 R5 R1 R4 G3 R3 R2 R11 R8 G1 R10 R9 44
22. R-trees: Insert ( ) G2 R7 R6 R5 R1 R4 G3 R3 R2 R11 R8 G4 R10 R9 G1 46 Solution 2
23. R-trees: Insert ( ) – Có thể phải tách để tạo thêm các nút mới – Thêm 1 nút có thể phải thực hiện ở nhiều mức (level) – Tiêu chí tách: Tối thiểu tổng không gian chiếm bởi các MBR  Tránh phải quản lý các vùng không có DL  Giảm sự chồng chéo của các MBR tăng hiệu quả khi tìm kiếm – Có các thuật toán để xác định cách tách với độ phức tạp khác nhau 48
24. R-trees: Delete ( ) 50
25. R-trees: Lưu ý  SS-tree  SR-tree: kết hợp của R*-tree và SS-tree 52
26. Tổng kết  k-D trees: – Dễ cài đặt – Thêm/Tìm kiếm: Nếu cây có n nút có thể cây cũng có độ cao là n xem hoặc tìm kiếm DL có độ phức tạp O (n) – Thực tế: độ sâu tìm kiếm thường dài hơn Point Quadtree – Xóa: cần tìm nút thay thế (không phức tạp) – Truy vấn phạm vi : (kn1 1/ k ) 54
27. Tổng kết  R-trees: – Hiệu quả trong việc truy nhập đĩa (do nhiều vùng được lưu trên 1 nút cây ko quá cao), thích hợp với DL lớn Được sử dụng rộng rãi – Có thể không hiệu quả khi tìm kiếm nhất là truy vấn phạm vi do các MBR có thể giao nhau  R-tree: thích hợp cho DL lớn  DL có kích thước indexes nhỏ: MX-quadtree hợp lý 56
28. Curse of dimensionality  Các kỹ thuật đánh chỉ mục giảm nhanh khi số chiều dữ liệu tăng: curse of dimensionality – Số các vùng được phân hoạch tăng theo hàm mũ: kd  (d: số chiều, k: số phân hoạch trên 1 chiều) Nhiều vùng rỗng hoặc chỉ có 1 phần tử ko hiệu quả – Hiệu ứng biên: nếu câu truy vấn nằm gần biên của 1 vùng nhiều điểm « hàng xóm » ko hiệu quả trong tìm kiếm – Không gian của hyper-rectangle, hyper-sphere tăng theo hàm mũ theo d tìm kiếm toàn bộ KGian 58 – Kết quả tìm kiếm KNN không ổn định