Hà Nội-2005/12
KỸ THUẬT TÌM KIẾM NÂNG CAO
Bài 8
PGS.TS. Đặng Văn Đức

dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Nội dung

Giới thiệu

Giảm thiểu không gian tìm kiếm

Cấu trúc dữ liệu dạng cây

Kết luận
2/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
1. Giới thiệu

Đã nghiên cứu các phương pháp/kỹ thuật tìm các véctơ đặc trưng của đối tượng đa phương tiện
(văn bản, âm thanh, hình ảnh và video)

Đã nghiên cứu phương pháp ước lượng độ tương tự và khoảng cách giữa các đối tượng trên cơ
sở véctơ đặc trưng

Véctơ đặc trưng là đa chiều

Với văn bản: Tổng số chiều véctơ đặc trưng là tổng số khái niệm trong các văn bản

Tổng số chiều của biểu đồ màu trong ảnh bằng tổng số bins màu


4/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Yêu cầu chung về cấu trúc dữ liệu

Kỹ thuật và cấu trúc dữ liệu hiệu quả cần hỗ trợ cả ba tiệm cận truy vấn, bao gồm

Điểm, dải và k-láng giềng gần nhất.

Hỗ trợ các thao tác cơ bản của MMDBMS như

Tìm kiếm, chèn, xóa

Tiêu chí quan trọng nhất:

Tìm kiếm hiệu quả

Việc tìm kiếm được thực hiện on-line và lặp nhiều lần.

Thao tác cần thiết nhưng không phải là then chốt:

Chèn, xóa

Chèn, xóa thường được thực hiện off-line và có thể theo lô.
5/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
2. Giảm thiểu không gian tìm kiếm

Một số kỹ thuật hay được sử dụng

Lọc bằng phân lớp, thuộc tính có cấu trúc hay từ khóa


Hầu hết các độ đo khoảng cách đặc trưng là độ đo metric và thỏa mãn tính chất bất đẳng thức
tam giác

Khoảng cách giữa hai đối tượng không thể nhỏ hơn hiệu khoảng cách giữa chúng tới đối tượng khác.
trong đó, d-độ đo khoảng cách, i, q, k - các véctơ đặc trưng

Bất đẳng thức trên đúng với mọi k, khi đối sánh nhiều đặc trưng ta có:
trong đó, m-tổng số đặc trưng sử dụng để đối sánh
8/42
),(),(),( kqdkidqid −≥
),(),(max),(
1 jjmj
kqdkidqid −≥
≤≤
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Các bước áp dụng bất đẳng thức tam giác

Chọn m véctơ đặc trưng để làm cơ sở đối sánh, m nhỏ hơn tổng số đối tượng n trong CSDL. Có
thể chọn ngẫu nhiên.

Thực hiện off-line:

Tính khoảng cách d(i,k
j
) giữa mỗi đối tượng i trong CSDL và véctơ so sánh vừa lựa chọn k
j
, lưu trữ chúng
trong CSDL.



Giả sử tìm các ảnh trong CSDL có khoảng cách đến véctơ truy vấn q nhỏ hơn 3: Kết quả sẽ là i
1

và i
7
.
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Trong CSDL d(i, k
1
) d(i,k
2
) |d(i,k
1
)-d(q,k
1
)| |d(i,k
2
)-d(q,k
2
)| l(i)
i
1
2 5 1 1 1
i
2
4 9 1 5 5
i
3
7 2 4 2 4

Phương pháp cây phân cấp

Input: O – Danh sách các đối tượng trong CSDL

Out: T – Cây phân cấp
1. Gán mỗi tài liệu của O vào cụm riêng, tạo lập danh sách các cụm L (khởi đầu giá trị
lá của T):
L = O1, O2, O3, , On-1, On.
2. Tính toán véctơ đại diện của từng cặp phần tử trong L để tìm ra hai cụm gần nhất
{Oi, Oj}.
3. Hủy bỏ Oi và Oj khỏi L.
4. Trộn Oi và Oj để hình thành nút mới Oij trong T, nó là cha của Oi và Oj trong cây
kết quả.
5. Lặp lại bước (2) cho đến khi chỉ còn một tập.
O1
O3
O6
O7
O8O2
O5 O4
O2
O5
O8
O4
O1
O3
O6
O7
12/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS


Khoảng cách d
avg
bằng khoảng cách nhỏ nhất được tính toán trên biểu đồ màu đầy đủ.

Vậy, có thể lựa chọn các đối tượng ứng viên trên cơ sở d
avg
trước khi tính toán khoảng cách với biểu đồ màu đầy đủ.
T
avgavgavg
BGRx ),,(=
14/42
P
pB
B
P
pG
G
P
pR
R
P
p
avg
P
p
avg
P
p
avg

Khi tìm kiếm: cần ít nhất M phép nhân véctơ N chiều.

Ý tưởng cơ bản của LSI (Chỉ mục ngữ nghĩa ẩn)

Nhóm các Terms tương đồng (cùng phạm trù) để hình thành chủ đề / khái niệm (Concepts) làm đại diện tài
liệu.

Ví dụ, các thuật ngữ pepper, spacy và hot có cùng phạm trù.

Do tổng số khái niệm nhỏ hơn nhiều so với tổng số thuật ngữ, cho nên đòi hỏi ít bộ nhớ lưu trữ hơn và thời gian tính toán sẽ nhanh
hơn.

Sử dụng tính chất toán của ma trận term-document (tính toán ma trận) để xác định các khái niệm.
15/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Mô hình LSI
16/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Phương pháp LSI

Nhiệm vụ:

Nhận dạng và tính toán “concepts” bằng cách nào?

Xem xét ma trận term-doc

Gọi A là ma trận term-doc với M cột (Terms) và N hàng (Docs).

Các phần tử của ma trận là trọng số w
i,j


Nhiệm vụ của LSI:

Tách các đặc trưng chủ yếu của ma trận term-doc A
T
và xấp xỉ nó bởi các ma trận nhỏ hơn.

Kỹ thuật sử dụng: SVD (tách giá trị số ít)

Ma trận các số thực A với kích thước MxN có thể biểu diễn bởi
A = UxSxV
T
trong đó, U - ma trận trực giao kích thước Mxr
V - ma trận trực giao kích thước Nxr
S - ma trận diagonal rxr với các giá trị sắp xếp giảm dần,
r - bậc của A, và r = min(M,N).

Cấu trúc của SVD

U là ma trận các véctơ riêng nhận từ tính toán AxA
T

V
T
là ma trận các véctơ riêng nhận từ tính toán A
T
xA

Độ phức tạp thuật toán là O(n
3

Terms
=
MxN
Mxr
rxN
rxr
A
U
S
V
T
N
rrr
s
N
M
=
MxN
Mxs
sxNsxs
A
s
U
s
S
s
V
T
s
Document vectors

Tổ chức dữ liệu theo dạng cây nhằm giảm số lần xâm nhập đĩa.

Tìm kiếm tuần tự rất chậm.

Cấu trúc cây

Tầng, nút

Mỗi nút có nhiều cành con.

Tổng số lần xâm nhập đĩa tương ứng với “độ sâu” của cây.

Chú ý khi sử dụng cấu trúc cây

Mỗi nút trong và lá của cây có kích thước tương ứng một blốc I/O dữ liệu.

Một hoặc hai tầng cây nên để thường trú trong bộ nhớ chính để tăng tốc độ xâm nhập.
22/42
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Cấu trúc dữ liệu cây B+

Cây B+ được sử dụng để tổ chức các vector đặc trưng một chiều

Nó là cơ sở để phát triển các cây dữ liệu đa chiều

B+ có cấu trúc phân cấp với nhiều nút.

Mỗi nút (kể cả gốc và lá) chứa n con trỏ và n-1 khóa

Gọi n là bậc của cây, tương đương số cành mà một nút có.

4. Hủy bản ghi với giá trị khóa 70
Nếu cây B+ có bậc n và có N bản ghi thì số lần xâm nhập (đĩa) là O(log
n
N)
24/27
dvduc-2005/12 Bài 8: Nâng cao hiệu năng MMDBMS
Qui tắc xây dựng cây B+

Cây phải cân đối: Mọi đường dẫn từ gốc đến nút lá phải có cùng độ dài.

Nút gốc phải có ít nhất 02 cành, trừ khi cây chỉ có 01 bản ghi.

Nếu cây có bậc n thì mỗi nút (trừ nút gốc và các nút lá) phải có từ n/2 đến n con trỏ.

Nếu cây có bậc n thì tổng số giá trị khóa trong nút lá phải ở trong khoảng từ (n-1)/2 đến n-1.

Tổng số giá trị khóa chứa trong nút không phải là lá sẽ nhỏ hơn tổng số con trỏ 1 đơn vị.

Mỗi nút lá có m/2 đến m dữ liệu. Thực tế m << n.
25/42