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
Chương 3: Các cấu trúc dữ liệu
đa chiều
Nguyễn Thị Oanh
Bộ môn HTTT – Viện CNTT & TT
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
1. k-D trees
3
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
k-D trees
Là mở rộng của cây nhị phân
Ở mỗi mức, các bản ghi sẽ được chia theo giá trị của
1 chiều nhất định.
– Mức 0: giá trị chiều 0
– Mức 1: giá chị chiều 1, …
– Mức k-1: giá trị chiều k-1
5
– Mức k: giá trị chiều 0, …
VD: 2-D trees
6
VD: 3-D trees
x
y
z
x
Cây được xây dựng phụ thuộc vào thứ tự các điểm được
đưa vào
7
2-D trees
Cấu trúc 1 nút:
INFO
XVAL YVAL
RLINK
LLINK
Đị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&
P N.RLINK : P.YVAL N.YVAL
8
2-D trees
Ví dụ:
Thứ tự insert:
INFO
XVAL YVAL
Banja Luka
Derventa
Toslic
19
40
38
54
4
45
50
38
40
4
Tuzla
Sinji
9
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
Deletion in 2-D trees
T: 2-D tree
Nút cần xóa (XVAL, YVAL) = (x, y)
Thuật toán:
– Tìm N: N.XVAL = x & N.YVAL = y
– Nếu N là nút lá: đặt LLINK or RLINK của cha N về NULL
và giải phóng N. Kết thúc
– Nếu N là nút trong:
Tìm nút thay thế (R) ở trong 2 cây con (Tf và T)
r
Thay các giá trị không phải con trỏ bằng giá trị của R
Lặp để xóa R
11
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
Tìm nút thay thế cho nút bị xóa:
Nếu N: mức chẵn
– Tr : không rỗng nút R trong cây con Tr có giá trị XVAL
nhỏ nhất là nút thay thế
– Tr : rỗng tìm nút thay thế bên cây Tl (How ?)
Tìm nút R’ bên cây trái Tl có XVAL nhỏ nhất
N.RLINK = N.LLINK, N.LLINK = NULL
Nút cần xóa
N
Tương tự nếu N ở mức lẻ
Cây con
Cây con
T
r
Tl
13
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
2-D trees k-D tree
p(x1, x2, .., xk)
INFO VAL[1] VAL[2] … VAL[k]
LLINK
RLINK
N: 1 nút thuộc k-D tree nếu
– Mọi nút M thuộc cây bên trái của N: M.VAL[i] <N.VAL[i]
– Mọi nút P thuộc cây bên phải của N: P.VAL[i] >=N.VAL[i]
i = level(N) mod k
15
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
2. Cây tứ phân dạng điểm
(Point Quadtrees)
17
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
SW
NE
SE
YVAL
XVAL
18
Cây tứ phân dạng điểm
Mỗi nút trong cây tứ phân ngầm biểu diễn 1 vùng:
19
Thêm DL vào cây tứ phân
Banja Luka
(19, 45)
Derventa (40, 50)
Toslic
Toslic (38, 38)
Tuzla (54, 40)
Sinji (4,4)
Tuzla
20
Tải về để xem bản đầy đủ
59 trang
26/04/2022
7700
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_co_so_du_lieu_da_phuong_tien_chuong_3_cac_cau_truc.pdf
