Luận án Khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy

: dữ liệu thưa (BMS-WebView1, FIFA), dữ liệu dày (Bible, Leviathan, Sign). 
Ngoài ra, các bộ dữ liệu giả định cũng được sử dụng được sinh từ phần mềm IBM 
Data Generator [2] với số lượng các thông số khác nhau để minh họa các kiểu dữ liệu 
khác nhau. Các bộ dữ liệu thử nghiệm còn được bổ sung các thông tin về giá trị 
khoảng cách thời gian và các giá trị lợi ích trong và lợi ích ngoài nhằm mô phỏng các 
thông tin của dữ liệu trong thực tế. Các giá trị này đều được sinh ngẫu nhiên trước 
khi khai phá. Trong thực tế, các mục có giá trị (trọng số) cao thì thường có tần xuất 
* ( 
 62 
xuất hiện thấp. Vì vậy các giá trị trọng số (lợi ích ngoài) trong các thử nghiệm cũng 
được sinh ngẫu nhiên theo phân phối chuẩn. 
 Cụ thể, luận án sẽ tập trung nghiên cứu đề xuất và giải quyết vấn đề sau đây: 
 - Vấn đề 1: trong việc xác định vấn đề nghiên cứu của luận án là phát triển 
 và đề xuất thuật toán khai phá top-k mẫu dãy thường xuyên trọng số với 
 khoảng cách thời gian trong đó quan tâm đến cả đến trọng số của mỗi mục 
 trong dãy dữ liệu và khoảng cách thời gian giữa các dãy trong CSDL dãy 
 có khoảng cách thời gian. Nội dung này sẽ được trình bày chi tiết trong 
 Chương 2. 
 - Vấn đề 2 trong việc xác định vấn đề nghiên cứu của luận án là phát triển 
 và đề xuất các thuật toán khai phá mẫu dãy lợi ích cao trong CSDL dãy 
 định lượng có khoảng cách thời gian trong đó quan tâm cả đến trọng số 
 của mỗi mục trong dãy dữ liệu, giá trị định lượng của mỗi mục dữ liệu và 
 khoảng cách thời gian giữa các dãy trong CSDL dãy định lượng có khoảng 
 cách thời gian. Nội dung này sẽ được trình bày chi tiết trong Chương 3. 
 63 
 CHƯƠNG 2. KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ 
 DỮ LIỆU DÃY CÓ KHOẢNG CÁCH THỜI GIAN 
 Trong chương 1, luận án đã phân tích các vấn đề cần được nghiên cứu về phát 
hiện mẫu dãy có trọng số trong các CSDL dãy, CSDL dãy có khoảng cách thời gian, 
CSDL dãy định lượng có khoảng cách thời gian. Ở chương này, luận án sẽ tập trung 
trình bày giải quyết nội dung thứ 1 về vấn đề khai phá top-k mẫu dãy thường xuyên 
trọng số có khoảng cách thời gian. 
 Vấn đề phát hiện top-k mẫu dãy thường xuyên trọng số trên CSDL dãy có 
khoảng cách thời gian được thực hiện bắt đầu bằng việc nghiên cứu thuật toán TKS 
[21] do Fournier-Viger và cộng sự đề xuất thực hiện khai phá top-k mẫu dãy thường 
xuyên trong CSDL dãy sử dụng biểu diễn CSDL theo chiều dọc và thuật toán khai 
phá mẫu dãy thường xuyên trọng số có khoảng cách thời gian WIPrefixSpan [40] đã 
được NCS và đồng sự đề xuất nhằm tiếp tục thực hiện nghiên cứu và đề xuất thuật 
toán TopKWFP đã được đăng trên tạp chí Journal of Computer Science and 
Cybernetics [CT1]. 
2.1. Giới thiệu 
 Các thuật toán khai phá mẫu dãy thường xuyên cổ điển AprioriAll [2], FreeSpan 
[13], PrefixSpan [31], Spam [30], Spade [11], Lapin-Spam [18], CM-Spade, CM-
Spam [17] có một số hạn chế: thứ nhất là các mục trong CSDL dãy có độ quan trọng 
như nhau nhưng trên thực tế mỗi mục có độ quan trọng khác nhau. Thứ 2, các mẫu 
dãy đều có dữ liệu về thời gian xảy ra sự kiện trong mẫu dãy đó nhưng các dữ liệu 
này đều bị bỏ qua. Thứ 3, các giải thuật cần xác định một ngưỡng tối thiểu minsup 
tuy nhiên thực tế thì rất khó xác định một ngưỡng tối thiểu phù hợp; một ngưỡng tối 
thiểu quá cao sẽ bỏ qua rất nhiều các mẫu dãy có giá trị, trong khi một ngưỡng tối 
thiểu thấp sẽ có thể tạo ra quá nhiều mẫu dãy không cần thiết. 
 Để giải quyết vấn đề thứ nhất, có thể gán cho mỗi mục trong CSDL một giá trị 
trọng số thể hiện mức độ quan trọng của mục đó. Các thuật toán khai phá mẫu dãy 
với trọng số có thể kể tới là [33], [50]. 
 64 
 Để giải quyết vấn đề thứ 2, các giá trị thời gian của các mẫu dãy đều phải được 
tính đến. Các với mẫu dãy khoảng cách thời gian giữa các thành phần trong dãy lớn 
thì sẽ có ít giá trị hơn các mẫu dãy có khoảng cách nhỏ. Các thuật toán khai phá mẫu 
dãy với khoảng cách thời gian đã được đề xuất với các cách tiếp cận khác nhau như 
trong [38], [39], [37], [53]. 
 Để giải quyết vấn đề thứ 3, bài toán khai phá top-k mẫu dãy thường xuyên đã ra 
đời. Một số thuật toán khai phá top-k có thể kể tới như [54], [55], [21], [56], [57], 
[58], [59]. Các thuật toán này được các tác giả đề xuất để tìm các mẫu có tần suất 
xuất hiện cao nhất. Trong khai phá các mẫu dãy thông thường, người dùng thường 
khó đặt ngưỡng tối thiểu bằng cách sử dụng các thuật toán khai thác mẫu dãy truyền 
thống nếu người dùng không có kiến thức nền tảng về cơ sở dữ liệu. Nếu ngưỡng tối 
thiểu được đặt quá thấp, quá nhiều mẫu dãy có thể được tìm thấy và các thuật toán có 
thể trở nên rất chậm và nếu ngưỡng tối thiểu được đặt quá cao, có thể tìm thấy quá ít 
mẫu dãy. Các thuật toán khai thác mẫu dãy top-k giải quyết vấn đề này bằng cách cho 
phép người dùng trực tiếp chỉ ra số lượng mẫu k được tìm thấy thay vì sử dụng tham 
số minsup. Khai phá mẫu dãy top-k là một vấn đề khó hơn khai phá mẫu dãy thông 
thường [21]. Các thuật toán tìm top-k mẫu thường xuyên kể trên chỉ quan tâm tới tần 
suất xuất hiện của các mẫu dãy mà chưa tính tới yếu tố khoảng cách thời gian và mức 
độ quan trọng của từng mục dữ liệu. 
 Thuật toán WIPrefixSpan [40] khai phá mẫu dãy thường xuyên có trọng số với 
khoảng cách thời gian. WIPrefixSpan không chỉ quan tâm tới khoảng cách thời gian, 
tần xuất xuất hiện của từng mẫu dãy mà còn quan tâm tới giá trị (trọng số) của từng 
mục dữ liệu. Mặc dù WIPrefixSpan có thể tìm ra các mẫu dãy thường xuyên có trọng 
số với khoảng cách thời gian dựa trên ngưỡng tối thiểu wminsup và các ràng buộc 
thời gian C1, C2, C3, C4 nhưng rất khó để xác định được ngưỡng tối thiểu wminsup 
thích hợp để tìm được các mẫu dãy có giá trị. Bởi vì có rất nhiều yếu tố ảnh hưởng 
tới kết quả tìm được như: độ phân bố của các mục dữ liệu và trọng số, mật độ của cơ 
sở dữ liệu, độ dài của các dãy Với cùng một ngưỡng hỗ trợ, một số bộ dữ liệu sẽ 
cho ra hàng triệu mẫu dãy, một số khác lại không cho ra kết quả nào. 
 65 
 Các khái niệm cơ bản trong khai phá mẫu dãy có trọng số trong CSDL dãy với 
khoảng cách thời gian đã được trình bày trong Mục 1.3 của Chương 1. Ngoài ra, trong 
phạm vi bài toán khai phá top-k mẫu dãy được kế thừa và tiếp tục phát triển từ thuật 
toán WIPrefixSpan [40] và thuật toán TKS [21] . Trên thực tế, bài toán tìm top-k mẫu 
dãy thường xuyên trọng số với khoảng cách thời gian sẽ có nhiều điểm khác biệt so 
với các thuật toán tìm top-k mẫu dãy thông thường và do đó cũng mang lại nhiều 
thách thức hơn. Để giải quyết vấn đề tìm top-k mẫu dãy thường xuyên trọng số với 
khoảng cách thời gian, chúng tôi đề xuất giải thuật TopKWFP. Thuật toán TopKWFP 
giải quyết 3 vấn đề: trọng số, khoảng cách thời gian và top-k mẫu dãy. Các thử nghiệm 
cho thấy thuật toán hiệu quả trong việc giải quyết bài toán đã đưa ra. 
2.2. Thuật toán khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách 
 thời gian (TopKWFP) 
2.2.1. Bài toán đặt ra 
 Bài toán khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách thời 
gian là tập các top-k các mẫu dãy thường xuyên trọng số trong CSDL dãy iSDB có 
khoảng cách thời gian. Bài toán như sau: 
 • Cho một CSDL dãy iSDB có khoảng cách thời gian, mỗi mục ij I được gán 
 một trọng số wj, một số tự nhiên k, các ràng buộc khoảng cách thời gian C1, 
 C2, C3, C4. 
 • Một dãy t được gọi là một dãy thuộc top-k mẫu dãy thường xuyên trọng số với 
 khoảng cách thời gian nếu có ít hơn k dãy có độ hỗ trợ với trọng số chuẩn hóa 
 lớn hơn NWSupport(t) và t thỏa mãn các ràng buộc thời gian C1, C2, C3, C4. 
 Giá trị wminsup tối ưu được định nghĩa là: 휀 = min{NWSupport(t)|t ∈ Τ }. 
 Với Τ là tập các top-k mẫu dãy thường xuyên trọng số với khoảng cách thời 
 gian. 
 Bài toán đặt ra: Phát hiện top-k các các mẫu dãy thường xuyên trọng số trong 
CSDL dãy iSDB có khoảng cách thời gian 
 66 
2.2.2. Ý tưởng thuật toán 
 Thuật toán TopKWFP dựa trên thuật toán WIPrefixSpan [40] là thuật toán sử 
dụng cơ sở dữ liệu tiền tố và phương pháp tăng trưởng mẫu dãy và thuật toán TKS 
[21] là thuật toán khai phá top-k mẫu dãy cổ điển. Đầu tiên, thuật toán TopKWFP cơ 
bản với chiến lược tăng dần ngưỡng hỗ trợ wminsup, sau đó bổ sung một chiến lược 
hiệu quả để tạo ứng viên hứa hẹn nhất. 
 - Tăng dần ngưỡng hỗ trợ wminsip: Chiến lược TopKWFP1: Đặt 
 wminsup=0. Duyệt CSDL iSDB và tìm các mẫu dãy thường xuyên bằng 
 cách áp dụng phương pháp tăng trưởng mẫu dãy. Mỗi khi một mẫu dãy 
 được tìm thấy, nó sẽ được đưa vào một danh sách L các mẫu dãy được sắp 
 xếp theo độ hỗ trợ có trọng số NWSupport. Danh sách này được sử dụng 
 để lưu các mẫu dãy đã được tìm thấy. Khi có đủ k mẫu dãy trong danh 
 sách L, giá trị wminsup sẽ được tăng lên bằng với NWSupport của mẫu 
 dãy có giá trị NWSupport nhỏ nhất trong L. Việc tăng giá trị wminsup sẽ 
 giúp giảm bớt không gian tìm kiếm. Sau khi tăng wminsup, các mẫu dãy 
 thường xuyên tìm được sẽ được đưa vào L, các mẫu dãy trong L không 
 thỏa mãn giá trị wminsup mới sẽ bị loại ra khỏi L và giá trị wminsup sẽ 
 được tiếp tục tăng lên bằng với giá trị NWSupport của mẫu dãy có 
 NWSupport nhỏ nhất trong L. Thuật toán tiếp tục đến khi không thể tìm 
 ra được mẫu dãy nào nữa, khi đó thuật toán kết thúc và đưa ra top-k mẫu 
 dãy thường xuyên. Tuy nhiên, nếu chỉ áp dụng chiến lược tăng độ hỗ trợ, 
 giải thuật sẽ không có hiệu suất tốt. 
 - Tạo các ứng viên hứa hẹn nhất: Chiến lược TopKWFP2: Để tăng hiệu suất 
 của giải thuật, sử dụng chiến lược là tìm cách tăng trưởng các mẫu dãy 
 ứng viên hứa hẹn nhất. Nghĩa là tìm cách tạo ra các ứng viên có 
 NWSupport lớn trước, nhờ vậy ngưỡng hỗ trợ wminsup sẽ tăng nhanh hơn 
 và không gian tìm kiếm cũng sẽ được giảm xuống. Cách làm này là sử 
 dụng một tập ứng viên hứa hẹn nhất R để lưu các ứng viên mẫu dãy thường 
 xuyên có trọng số. Sau đó thuật toán TopKWFP luôn mở rộng các mẫu 
 dãy ứng viên có NWSupport lớn nhất trong R trước. 
 67 
 Ý tưởng thuật toán thực hiện như sau 
 - Bước 1: Thuật toán TopKWFP 
 - đầu tiên khởi tạo các giá trị tập R, L bằng rỗng và wminsup=0. Sau đó 
 duyệt CSDL lần đầu để tìm các mục i trong CSDL và giá trị maxW. Với 
 mỗi mục i, ghép giá trị = , thực hiện kiểm tra điều kiện 
 support( )* maxW wminsup, nếu thỏa mãn thì đưa vào tập ứng viên 
 R. Kiểm tra tiếp điều kiện support( )*NW( ) wminsup, nếu thỏa mãn 
 thì gọi thủ tục SAVE. 
 - Bước 2: Tiếp theo, duyệt CSDL lần 2 để loại bỏ các mục không phải là 
 ứng viên. Thực hiện vòng lặp while lấy giá trị ứng viên r có NWSupport 
 lớn nhất trong tập L. Sau đó thực hiện xây dựng CSDL tiền tố iSDB|r và 
 gọi thủ tục Projection để sinh mẫu dãy. 
 Thủ tục Projection thực hiện duyệt CSDL tiền tố iSDB|r để sinh các ứng viên 
đưa vào tập L. Đầu tiên, duyệt CSDL iSDB|r để tìm các cặp (∆t; i) thỏa mãn các điều 
kiện wminsup và C1, C2. Sau đó với mỗi mục tìm thấy, thực hiện ghép cặp r = <r, 
(∆t; i)> để tạo thành mẫu dãy mới. Kiểm tra điều kiện C4 với mẫu dãy r mới tạo thành, 
nếu thỏa mãn C4 thì đưa vào tập ứng viên R và kiểm tra tiếp điều kiện C3, nếu r thỏa 
mãn C3 thì gọi thủ tục SAVE để đưa r vào danh sách L. 
 Thủ tục SAVE thực hiện tăng giá trị wminsup và cập nhật danh sách L mỗi 
khi tìm thấy một mẫu dãy thường xuyên r. Đầu tiên, thêm r vào L, nếu L có nhiều 
hơn k mẫu dãy và độ hỗ trợ có trọng số của r lớn hơn wminsup thì loại bỏ các mẫu 
dãy có NWSupport thấp nhất trong L sao cho L chỉ còn lại k mẫu dãy. Cuối cùng, đặt 
giá trị wminsup mới bằng với giá trị NWSupport nhỏ nhất trong L. 
2.2.3. Thuật toán TopKWFP 
 Thuật toán được minh họa như Thuật toán 2.1 như sau: 
Thuật toán 2.1. Thuật toán TopKWFP 
input: iSDB: CSDL dãy có khoảng cách thời gian 
 W: Bảng giá trị trọng số của các mục i: wi W 
 68 
 k: Giá trị số xác định top-k mẫu dãy 
 C1, C2, C3, C4: Giá trị ràng buộc khoảng cách thời gian 
output: Tập top-k các mẫu dãy thường xuyên trọng số với khoảng khách thời gian 
Thủ tục TopKWFP (iSDB,W(i), C1,C2,C3,C4,k) 
1. Start 
2. R= ∅; L= ∅; wminsup=0; 
3. Duyệt iSDB lần đầu 
4. Begin 
5. Đếm giá trị hỗ trợ sup(i) của mỗi mục i trong iSDB; 
6. Tính giá trị MaxW = max{W(i)}; 
7. End; 
8. For earch mỗi mục i trong iSDB 
9. = ; 
10. If sup( )*maxW wminsup then 
11. R = R  ; 
12. End if; 
13. If sup( )*NW( ) wminsup then 
14. SAVE( ,L,k,wminsup) 
15. End if; 
16. End For; 
17. If k < số lượng mục i trong iSDB then 
18. Duyệt iSDB thứ hai 
19. Begin 
20. Xây dựng lại CSDL iSDB bằng cách loại bỏ tất cả các mục i 
 trong iSDB không thỏa mãn điều kiện sup( )*maxW 
 wminsup; 
21. End; 
22. End if; 
23. While ∃ ∈ 푅 và sup(r)*maxW wminsup do 
 69 
24. r = mẫu dãy có sup(r)*NW(r) lớn nhất trong R; 
25. Xây dựng cơ sở dữ liệu tiền tố r là iSDB|r; 
26. PROJECTION(iSDB|r,W(i),C1,C2,C3,C4,wminsup,k); 
27. Loại bỏ r trong R; 
28. Loại bỏ khỏi R tất cả các mục s thỏa mãn điều kiện sup(s)*maxW<= 
 wminsup; 
29. End while; 
30. Rerurn L; 
31. End. 
 Thủ tục PROJECTION(iSDB|r,W(i),C1,C2,C3,C4,wminsup,k) thực hiện 
duyệt CSDL tiền tố iSDB|r để sinh các ứng viên đưa vào tập L. Đầu tiên, duyệt CSDL 
iSDB|r để tìm các cặp (∆t; i) thỏa mãn các điều kiện wminsup và C1, C2. Sau đó với 
mỗi mục tìm thấy, thực hiện ghép cặp r = để tạo thành mẫu dãy mới. 
Kiểm tra điều kiện C4 với mẫu dãy r mới tạo thành, nếu thỏa mãn C4 thì đưa vào tập 
ứng viên R và kiểm tra tiếp điều kiện C3, nếu r thỏa mãn C3 thì gọi thủ tục SAVE để 
đưa r vào danh sách L.Thực hiện như sau:. 
Thủ tục PROJECTION(iSDB|r,W(i),C1,C2,C3,C4,wminsup,k) 
1. Start 
2. Duyệt iSDB|r để tìm tất cả các cặp (∆t; i) thỏa mãn sup(i)*maxW wminsup, 
 C1 và C2, với i là một mục dữ liệu, ∆t là khoảng cách thời gian giữa r và i; 
3. For each (∆t; i) 
4. r = ; 
5. If r satisfies C4 then 
6. R = R  r; 
7. If r satisfies C3 and sup(r)*NW(r) wminsup then 
8. SAVE(r,L,k,wminsup); 
9. End if; 
10. End if; 
 70 
11. End For; 
12. End. 
 Thủ tục SAVE thực hiện tăng giá trị wminsup và cập nhật danh sách L mỗi 
khi tìm thấy một mẫu dãy thường xuyên r. Đầu tiên, thêm r vào L, nếu L có nhiều 
hơn k mẫu dãy và độ hỗ trợ có trọng số của r lớn hơn wminsup thì loại bỏ các mẫu 
dãy có NWSupport thấp nhất trong L sao cho L chỉ còn lại k mẫu dãy. Cuối cùng, đặt 
giá trị wminsup mới bằng với giá trị NWSupport nhỏ nhất trong L. Thực hiện như 
sau: 
Thủ tục SAVE (r,L,k,wminsup) 
1. Start 
2. L= L {r}; 
3. If |L| > k then 
4. If NWSupport(r) > wminsup then 
5. While |L| > k and ∃s ∈ L| NWSupport(s) = wminsup 
6. Loại bỏ s trong L. 
7. End while; 
8. End if; 
9. wminsup = giá trị NWSupport nhỏ nhất trong L; 
10. End if; 
11. End. 
2.2.4. Phân tích thuật toán TopKWFP 
 Một mẫu dãy ∈ 퐿 được tìm bởi thuật toán TopKWFP, ta phân tích các 
bước thuật toán để khai phá được là một mẫu dãy thường xuyên trọng số với 
khoảng cách thời gian. Đồng thời nằm trong tập kết quả các mẫu dãy trọng số với 
khoảng cách thời gian L và kích thước của L gồm k mẫu dãy. 
 71 
2.2.4.1. Phân tích TopKWFP 
 Dòng lệnh 2 thực hiện khởi tạo tập R (Tập các ứng viên mẫu dãy trọng số với 
khoảng cách thời gian) bằng rỗng, tập L (Tập các kết quả top-k mẫu dãy trọng số với 
khoảng cách thời gian) bằng rỗng, giá trị wminsup = 0. 
 Từ dòng lệnh 3 đến dòng lệnh 7 nhằm thực hiện duyệt toàn bộ CSDL iSDB 
lần đầu, tính giá trị độ hỗ trợ của mỗi mục i trong iSDB trong dòng lệnh 5, xác định 
giá trị MaxW là giá trị lớn nhất của các trọng số các mục i trong iSDB. 
 Từ dòng lệnh 8 đến dòng lệnh 16 thực hiện vòng lặp duyệt tất cả các mục i 
trong iSDB. Với mỗi mục i, thực hiện ghép để xây dựng mẫu dãy = trong 
đó giá trị 0 là giá trị thời gian bắt đầu, i là mục dữ liệu tại dòng lệnh 9. Kiểm tra điều 
kiện sup( )*maxW wminsup tại dòng lệnh 10 và nạp dãy vào tập R tại dòng lệnh 
số 11. Do lúc này giá trị wminsup =0 nên tất cả các mẫu dãy đều được đưa vào tập 
R. Kiểm tra điều kiện sup( )*NW( ) wminsup tại dòng lệnh 13, do ban đầu 
wminsup = 0 nên thỏa mãn và thực hiện thủ tục SAVE() tại dòng lệnh 14. Tuy nhiên 
trong thủ tục SAVE() có dòng lệnh 9 nhằm tăng dần giá trị wminsup lên với các điều 
kiện kích thước tập |L| > k, vì vậy các mục tiếp theo khi khai thác sẽ nhận các giá trị 
wminsup mới. 
 Từ dòng lệnh số 17 đến dòng lệnh số 21 thực hiện kiểm tra giá trị k so với số 
lượng mục i trong iSDB. Trong trường hợp k<i thì duyệt và xây dựng lại CSDL 
QiSDB bằng cách loại bỏ tất cả các mục i không thỏa mãn điều kiện 
sup( )*maxW wminsup tại dòng lệnh 20. Trường hợp này ít xảy ra do thông thường 
giá trị k đưa vào lớn hơn rất nhiều số lượng các mục i trong CSDL QiSDB. 
 Từ dòng lệnh 23 đến dòng lệnh 29 thực hiện khai phá tất cả các mẫu dãy có 
trong tập ứng viên R và thực hiện khai phá đệ quy bởi thủ tục PROJECTION() đối 
với các mẫu dãy tăng trưởng với tiền tố r ban đầu. Dòng lệnh 23 thực hiện xử lý trong 
khi R ∅ thì xử lý đối với mỗi mẫu dãy ứng viên ∃ ∈ 푅 và kiểm tra giá trị 
sup(r)*maxW wminsup, nếu thỏa mãn thì thực hiện các bước tiếp theo. Dòng lệnh 
24 xác định mẫu dãy r là mẫu dãy có giá trị sup(r)*NW(r) trong R nhằm lựa chọn r 
là mẫu dãy có giá trị độ hỗ trợ với trọng số chuẩn hóa lớn nhất (Định nghĩa 1.21) để 
 72 
khai phá, câu lệnh này nhằm để tăng hiệu suất của giải thuật, sử dụng chiến lược là 
tìm cách tăng trưởng các mẫu dãy ứng viên hứa hẹn nhất. Câu lệnh 25 thực hiện xây 
dựng CSDL chiếu với tiền tố r là iSDB|r . Câu lệnh 26 nhằm khai phá đệ quy theo 
chiều sâu bởi thủ tục PROJECTION(iSDB|r,W(i),C1,C2,C3,C4,wminsup,k) trong đó 
thủ tục này các mẫu dãy ứng viên sẽ được tiếp tục nạp vào tập R và giá trị wminsup 
tiếp tục được tăng dần ngưỡng hỗ trợ. Dòng lệnh 27 thực hiện loại bỏ mẫu dãy r khỏi 
R do đã thực hiện khai phá xong mẫu dãy r. Dòng lệnh 28 thực hiện tỉa tất cả các dãy 
ứng viên trong R chứa mục s mà sup(s)*maxW≤wminsup nhằm giảm và tỉa bớt các 
dãy ứng viên trong R do giá trị wminsup đã thay đổi tăng ngưỡng hỗ trợ bên trong 
thủ tục PROJECTION(). 
 Dòng lệnh 30 là trả ra kết quả tập L là tập các kết quả top-k mẫu dãy trọng số 
với khoảng cách thời gian. 
2.2.4.2. Phân tích thủ tục PROJECTION 
 Dòng lệnh 2 thực hiện duyệt CSDL chiếu iSDB|r để tìm tất cả các cặp (∆t; i) 
thỏa mãn sup(i)*maxW wminsup, C1 và C2, với i là một mục dữ liệu, ∆t là khoảng 
cách thời gian giữa r và i; Câu lệnh này nhằm mục đích xây dựng các tìm các cặp 1 
phần tử (∆t; i) để ghép với dãy tiền tố r ban đầu từ CSDL chiếu thành các dãy mới và 
xác định xem dãy mới có thỏa mãn điều kiện thời gian C1 và C2 (điều kiện khoảng 
cách giữa hai dãy liền kề), đồng thời thỏa mãn sup(i)*maxW wminsup để chuẩn bị 
khai phá kiểm tra các điều kiện trong các câu lệnh tiếp theo. 
 Từ dòng lệnh 3 đến dòng lệnh 11 thực hiện vòng lặp duyệt tất cả các cặp (∆t;i) 
tìm thấy trong câu lệnh số 2. Dòng lệnh 4 thực hiện ghép r = nhằm xây 
dựng các dãy mới ghép với tiền tố r ban đầu (độ dài dãy r tăng thêm 1). Dòng lệnh 5 
thực hiện kiểm tra điều kiện thời gian C4 của dãy r (điều kiện khoảng cách lớn nhất 
giữa dãy đầu và dãy cuối trong r). Nếu thỏa mãn thì thực hiện nạp mẫu dãy r vào tập 
mẫu dãy ứng viên R tại dòng lệnh 6. Dòng lệnh 7 kiểm tra điều kiện thời gian C3 
(điều kiện khoảng cách thời gian nhỏ nhất giữa dãy đầu và dãy cuối) và giá trị 
sup(r)*NW(r) wminsup, nếu thỏa mãn thì thực hiện thủ tục đệ quy 
SAVE(r,L,k,wminsup); 
 73 
2.2.4.3. Phân tích thủ tục SAVE 
 Dòng lệnh 2 thực hiện nạp mẫu dãy r vào tập kết quả L. Các điều kiện kiểm 
tra được thực hiện ở các bước trong thủ tục PROJECTION(). 
 Dòng lệnh 3 nhằm kiểm tra kích thước của tập L so với giá trị k ban đầu, nếu 
|L| ≤ k thì thoát khỏi thủ tục, giá trị wminsup giữ nguyên và tiếp tục khai phá tiếp để 
nạp vào tập L, nếu |L| > k thì thực hiện các bước tiếp theo (nhằm tỉa bớt các mẫu dãy 
nhằm đảm bảo tìm được top-k mẫu dãy, đồng thời tăng dần ngưỡng hỗ trợ wminsup 
tiếp theo). 
 Dòng lệnh 4 kiểm tra điều kiện NWSupport(r) = wminsup, nếu thỏa mãn thì 
thực dòng lệnh 5 đến dòng lệnh 7 với vòng lặp điều kiện loại bỏ các dãy s sao cho 
|L|>k và ∃s ∈ L| NWSupport(s)=w