LỜI CAM ĐOAN
Trước khi đi vào nội dung bản luận văn thạc sĩ của mình, tôi xin cam đoan
luận văn này do chính tôi viết, dựa trên những kiến thức, hiểu biết của bản thân, sự
chỉ dẫn của cô giáo hướng dẫn và những thông tin mà tôi tìm hiểu, tham khảo được
qua các tài liệu liên quan. Các kết quả nêu trong luận văn là trung thực và chưa từng
được ai công bố trong các công trình nào khác.

Học viên
Đỗ Thị Thanh Loan


LỜI CẢM ƠN
Trên thực tế không có sự thành công nào mà không gắn liền với những sự
hỗ trợ, giúp đỡ dù ít hay nhiều, dù trực tiếp hay gián tiếp của người khác. Trong
suốt thời gian từ khi bắt đầu học tập ở giảng đường đại học đến nay, em đã nhận
được rất nhiều sự quan tâm, giúp đỡ của quý Thầy Cô, gia đình và bạn bè.
Với lòng biết ơn sâu sắc nhất, em xin gửi đến quý Thầy Cô Viện Công
nghệ thông tin và Truyền thông – Trường Đại Học Bách Khoa Hà Nội đã cùng với
tri thức và tâm huyết của mình để truyền đạt vốn kiến thức quý báu cho em trong
suốt thời gian học tập tại trường.
Em xin chân thành cảm ơn TS.Vũ Tuyết Trinh đã tận tâm hướng dẫn em
trong suốt quá trình làm luận văn. Nếu không có những lời hướng dẫn, dạy bảo của
cô thì em nghĩ bài luận văn này của em rất khó có thể hoàn thiện được. Một lần nữa,
em xin chân thành cảm ơn cô.
Trong quá trình làm không tránh khỏi những thiếu sót, em rất mong nhận
được những ý kiến đóng góp quý báu của quý Thầy Cô và các bạn học cùng lớp để
kiến thức của em được hoàn thiện hơn.
Sau cùng, em xin kính chúc quý Thầy Cô trong Khoa Công nghệ thông tin
thật dồi dào sức khỏe, niềm tin để tiếp tục thực hiện sứ mệnh cao đẹp của mình là
truyền đạt kiến thức cho thế hệ mai sau. Trân trọng.
TP. HN, ngày 20 tháng 9 năm 2014

Học viên thực hiện (ký và ghi họ tên).

2


MỤC LỤC

LỜI CAM ĐOAN.................................................................................................... 1
LỜI CẢM ƠN ......................................................................................................... 2
MỤC LỤC .............................................................................................................. 3
DANH MỤC CÁC HÌNH ....................................................................................... 4
Chương 1. GIỚI THIỆU BÀI TOÁN....................................................................... 5
1.1. Lý do lựa chọn đề tài ..................................................................................... 5
1.2. Mục đích đề tài .............................................................................................. 6
1.3. Bố cục của luận văn....................................................................................... 6
Chương 2. CƠ SỞ LÝ THUYẾT ............................................................................ 8
2.1. Phát biểu bài toán Top-k ................................................................................ 8
2.2. Thuật toán TA (Threshold Algorithm) ........................................................... 8
2.3. Thuật toán BPA(Best Position Algorithm)................................................... 12
2.4. Thuật toán TPUT(Three Phase Uniform Threshold) .................................... 16
2.5. Thuật toán TPAT(Three-Phase Adaptive-Threshold)................................... 20
2.6. Thuật toán TPOR(Three-Phase Object-Ranking) ......................................... 24
2.7. So sánh đánh giá các thuật toán TA, TPUT, TPOR...................................... 28
Chương 3. XÂY DỰNG ỨNG DỤNG QUẢN LÝ TRUYỆN CƯỜI
JOKESYSTEM SỬ DỤNG TRUY VẤN TOP-K .................................................. 29
3.1. Mô tả bài toán ............................................................................................. 29
3.2. Xây dựng hệ thống ...................................................................................... 29
3.3. Thử nghiệm ................................................................................................. 32
Chương 4. KẾT LUẬN ......................................................................................... 36
4.1. Tóm tắt kết quả............................................................................................ 36

4.2. Hướng phát triển ......................................................................................... 36
TÀI LIỆU THAM KHẢO ..................................................................................... 37

3


DANH MỤC CÁC HÌNH
Hình 1. Một ví dụ truy vấn top-k................................................................. 6
Hình 2. Ví dụ với ba hệ thống con. ........................................................... 10
Hình 3. Ví dụ cơ sở dữ liệu. a) 3 danh sách được sắp xếp. b) Ngưỡng TA ở
vị trí từ 1 tới 10. c)Tổng điểm của mỗi đối tượng dữ liệu. ...................................... 14
Hình 4. Mô hình quan hệ .......................................................................... 31
Hình 5. Giao diện chương trình ................................................................. 31

4


Chương 1. GIỚI THIỆU BÀI TOÁN
1.1. Lý do lựa chọn đề tài
Một truy vấn trên cơ sở dữ liệu SQL trả về tất cả thông tin đáp ứng được
các điều kiện trong truy vấn. Có thể xảy ra hai trường hợp:
- Câu trả lời trống rỗng: khi câu truy vấn quá chọn lọc, quá nhiều lựa chọn,
không có thông tin nào thỏa mãn.
- Nhiều câu trả lời: khi truy vấn không phải là quá chọn lọc, câu truy vấn
quá rộng, thông tin trả về quá nhiều.
Trong hai trường hợp này người dùng sẽ có thể mong muốn nhận được một
số lượng vừa phải các dữ liệu cần tìm. Sử dụng truy vấn top-k thay cho truy vấn
thông thường để giải quyết hai vấn đề trên, truy vấn top-k định nghĩa như sau:
- Truy vấn Top-k nhằm mục đích lấy từ một tập thông tin trả về của một
truy vấn trên cơ sở dữ liệu SQL k thông tin mà có tổng điểm cao nhất. Tổng điểm

này được tính dựa trên sự kết hợp của nhiều điều kiện trong truy vấn.
Ví dụ 1. Cho cơ sở dữ liệu City gồm 2 bảng: Schools và Houses.

- Cơ sở dữ liệu Houses cung cấp một danh sách xếp hạng của những ngôi
nhà với giá rẻ nhất và vị trí của chúng
- Cơ sở dữ liệu Schools cung cấp một danh sách xếp hạng các trường chi
phí thấp nhất và vị trí của chúng
- Yêu cầu: Đưa ra 4 vị trí trong thành phố có chi phí kết hợp mua một ngôi
nhà và trả tiền học phí cho 10 năm tại vị trí đó là thấp nhất.

5


Hình 1. Một ví dụ truy vấn top-k.

Giải thích:
- 2 bảng Schools và Houses liên kết dựa vào vị trí ( trường Location).
- Để đánh giá độ phù hợp của Houses-Schools ta có thể sử dụng công thức
sau:
Chi phí = Price + 10* Tuition.
=> Kết quả cuối cùng của truy vấn là: 4 cặp Houses-Schools với chi phí
thấp nhất.
Đối với một số lượng lớn Schools và Houses, nếu xử lý truy vấn theo cách
truyền thống sẽ rất mất thời gian vì phải thao tác lệnh lựa chọn dữ liệu và sắp xếp
lại kết quả.
1.2. Mục đích đề tài
- Tìm hiểu về truy vấn top-k và một số thuật toán top-k. Phân tích và so
sánh thời gian thực hiện các thuật toán.
- Xây dựng được ứng dụng thử nghiệm áp dụng truy vấn top-k với tìm kiếm
full-text trên trường dữ liệu văn bản.

1.3. Bố cục của luận văn
Phần tiếp theo của luận văn được trình bày như sau:
6


- Chương 2. Cơ sở lý thuyết
- Chương 3. Xây dựng ứng dụng quản lý truyện cười JokeSystem sử dụng
truy vấn Top-k.
- Chương 4. Kết luận

7


Chương 2. CƠ SỞ LÝ THUYẾT
2.1. Phát biểu bài toán Top-k
Xét m danh sách dữ liệu đã được sắp xếp dựa vào kết quả của truy vấn
SQL.
- Đầu vào m danh sách chứa dữ liệu bao gồm các cặp <Oj,LocalScorei(Oj)>,
với: i=1..m (m là số danh sách đầu vào), j=1..n (n là số đối tượng trên m danh sách,
n>0, n ∈ N), trong đó Oj là đối tượng và LocalScorei(Oj) là điểm của đối tượng Oj,
mỗi đối tượng xuất hiện không phải chỉ trên một danh sách mà xuất hiện trên m
danh sách, tùy theo kết quả của truy vấn.
- Đầu ra: k đối tượng Oj có điểm tổng thể cao nhất. Trong đó, điểm tổng thể
GlobalScore(Oj) được tính như sau:
GlobalScore(Oj) = ∑(LocalScorei(Oj)), với i=1..m (m là số danh sách đầu
vào), j=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
- Ý tưởng: Không duyệt hết các kết quả có thể mà chỉ cần duyệt một phần
và đưa ra top-k kết quả có thứ tự.
- Nhiều thuật toán TA[3][1], BPA[1], TPUT[3], TPAT[3], TPOR[3] đã
được đề xuất cho phép tính tổng điểm mỗi đối tượng theo nhiều điều kiện và đưa ra

top-k kết quả thỏa mãn nhưng khác nhau về thời gian thực hiện thuật toán.
- Dựa vào kỹ thuật xử lý chia các thuật toán top-k ra làm 2 dạng:
+ Các thuật toán Ngưỡng: TA, BPA
+ Các thuật toán 3 pha: TPUT, TPAT, TPOR
2.2. Thuật toán TA (Threshold Algorithm)
Tư tưởng thuật toán TA[1][3]: Xét m danh sách đã được sắp xếp dựa vào các điều
kiện tìm kiếm của câu truy vấn. Duyệt lần lượt từng hàng của mỗi danh sách, sau đó
tính tổng điểm các đối tượng được tìm thấy. Tính giá trị ngưỡng của mỗi hàng, và

8


so sánh giá trị Ngưỡng với tổng điểm các đối tượng được tìm thấy. Quá trình duyệt
lần lượt từng hàng trên mỗi danh sách sẽ được lặp cho đến khi thỏa mãn có k đối
tượng lớn hơn hoặc bằng giá trị ngưỡng thì dừng thuật toán.
a. Các bước xây dựng thuật toán TA[1][3]:
Bước 1.
- Tính tổng điểm của mỗi đối tượng theo công thức:
GlobalScore(Oj) = ∑( LocalScorei(Oj)), với i=1..m (m là số danh sách đầu
vào), j=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Oj: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorei(Oj): điểm của đối tượng Oj.
+ GlobalScore(Oj): điểm tổng thể của đối tượng Oj.
- Sắp xếp lại danh sách kết quả sau khi tính tổng điểm mỗi đối tượng và đưa
ra k kết quả có tổng điểm cao nhất vào danh sách Y, với k là số kết quả theo yêu
cầu top-k ban đầu.
Bước 2. Tính ngưỡng N theo công thức:
N = ∑( LocalScorei(Oj)), với i=1..m (m là số danh sách đầu vào), j=1..n (n
là số đối tượng trên m danh sách, n>0, n ∈ N)

- So sánh mỗi đối tượng trong danh sách Y ở bước 1 với Ngưỡng.
+ Nếu đối tượng nào có tổng điểm lớn hơn hoặc bằng ngưỡng thì cho vào
danh sách kết quả Y và sắp xếp lại danh sách.
+ Nếu không có đối tượng nào thỏa mãn điều kiện lớn hơn hoặc bằng
ngưỡng thì thuật toán duyệt sang hàng tiếp theo và quay lại bước 1.
Thuật toán dừng khi có k đối tượng thoả mãn điều kiện lớn hơn hoặc bằng
ngưỡng.

9


Bước 3. Trả ra danh sách kết quả Y.
b. Ví dụ 2: Cho ví dụ với ba hệ thống con subsystem1, subsystem2, subsystem3.
Yêu cầu tìm top-2 đối tượng.

Hình 2. Ví dụ với ba hệ thống con.

Vị trí 1:
- Thuật toán TA duyệt hết các đối tượng hàng đầu tiên trong 3 hệ thống
con.
+ các đối tượng được nhìn thấy: O5, O4, và O3
=> giá trị ngưỡng tại thời điểm này được tính như sau:
N = 21 + 34 + 30 = 85.
- thuật toán TA tính tổng điểm mỗi đối tượng O5, O4, O3:
+ O5: ∑(O5) = 21 + 9 + 7 = 37,
+ O4: ∑(O4) = 11 + 34 + 14 = 59
+ O3: ∑(O3) = 11 + 26 +30 = 67.

10



=> TA duy trì top 2 đối tượng O3 và O4.
Tổng điểm của O3, O4 không lớn hơn giá trị ngưỡng hiện tại
=>TA tiếp tục duyệt các đối tượng tại vị trí thứ hai của tất cả các danh sách.
Vị trí 2:
- Tại thời điểm này, giá trị ngưỡng tính lại như sau:
N = 17 + 29 + 14 = 60.
+ Các đối tượng mới thấy là O1 và O2.
+ O1: ∑(O1) = 0 + 29 + 0 = 29
+ O2: ∑(O2) = 17 + 0 + 1 = 18.
+ O5: ∑(O5) = 21 + 9 + 7 = 37,
+ O4: ∑(O4) = 11 + 34 + 14 = 59
+ O3: ∑(O3) = 11 + 26 +30 = 67.
=> TA vẫn giữ đối tượng O3 và O4 vì tổng điểm cao hơn so với của O1 và
O2.
- Ta thấy chỉ có O3 có tổng điểm lớn hơn giá trị ngưỡng hiện tại là 60
=> thuật toán TA vẫn tiếp tục để quét các đối tượng ở vị trí thứ ba.
Vị trí 3:
- giá trị ngưỡng như sau:
N = 11 + 29 + 9 = 49
- đối tượng mới thấy là O0.
- TA tính tổng điểm cho O0:
∑(O0) = 38.
=> O3 và O4 vẫn duy trì hai tổng điểm cao nhất, ở vị trí 3 này đã lớn hơn
hoặc bằng giá trị ngưỡng hiện tại.
11


=> TA dừng vào thời điểm này và trả về O3 và O4 là top-2 đối tượng cần
tìm.

2.3. Thuật toán BPA(Best Position Algorithm)
Tư tưởng thuật toán BPA[1]: Duyệt lần lượt qua mỗi hàng của m danh sách đầu
vào, sau đó tính tổng điểm các đối tượng được tìm thấy. Sau khi tính tổng điểm mỗi
đối tượng xong, đem so sánh lần lượt mỗi đối tượng được tìm thấy sớm nhất đó với
từng đối tượng trên các hàng còn lại của m danh sách. Mục đích của việc so sánh là
để đưa ra vị trí tốt nhất của mỗi hàng. Tổng điểm của các vị trí tốt nhất sau khi so
sánh là giá trị ngưỡng. Sau khi xác định được giá trị ngưỡng, ta đem so sánh tiếp
từng tổng điểm của mỗi đối tượng được tìm thấy trên mỗi hàng với ngưỡng, nếu đối
tượng nào thỏa mãn lớn hơn hoặc bằng ngưỡng thì cho vào danh sách kết quả tạm
thời. Tiếp tục quá trình duyệt tiếp sanh hàng tiếp theo của m danh sách. Quá trình
này được lặp cho đến khi có k đối tượng thỏa mãn điều kiện lớn hơn hoặc bằng giá
trị ngưỡng thì dừng thuật toán.
a. Các bước xây dựng thuật toán BPA[1]:
Bước 1.
- Tính tổng điểm của mỗi đối tượng theo công thức:
GlobalScore(Oj) = ∑( LocalScorei(Oj)), với i=1..m (m là số danh sách đầu
vào), j=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Oj: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorei(Oj): điểm của đối tượng Oj.
+ GlobalScore(Oj): điểm tổng thể của đối tượng Oj.
- Sắp xếp lại danh sách kết quả sau khi tính tổng điểm mỗi đối tượng và đưa
ra k kết quả có tổng điểm cao nhất vào danh sách Y, với k là số kết quả theo yêu
cầu top-k ban đầu.

12


Bước 2.
Duyệt qua từng hàng trên mỗi danh sách, so sánh Oj với mỗi đối tượng trên

từng danh sách.
Thiết lập danh sách P chứa các đối tượng có vị trí được nhìn thấy gần nhất
trong mỗi danh sách m, sau khi thực hiện so sánh Oj với mỗi đối tượng trên từng
danh sách. Vị trí tốt nhất là vị trí được nhìn thấy gần nhất trước điểm mù.
Trong mỗi danh sách P lấy Oj có LocalScore cao nhất và thiết lập bp i là vị
trí tốt nhất hay có LocalScore cao nhất trong mỗi danh sách P đó.
Bước 3: Tính ngưỡng theo công thức:
N = ∑(bpi), với i=1..n(n là số đối tượng có vị trí tốt nhất trên m danh
sách, n>0, n ∈ N)
Nếu Y chứa GlobalScore(Oj) cao hơn hoặc bằng N thì Oj đó được lưu vào
trong danh sách kết quả L và được sắp xếp lại danh sách. Nếu không, đi đến 1.
Thuật toán dừng khi có k đối tượng thỏa mãn điều kiện GlobalScorek(Oj)
lớn hơn hoặc bằng N.
Bước 4: Trả ra L
b. Ví dụ 4

13


Hình 3. Ví dụ cơ sở dữ liệu. a) 3 danh sách được sắp xếp. b) Ngưỡng TA ở vị trí từ 1 tới
10. c)Tổng điểm của mỗi đối tượng dữ liệu.

- Xét tại vị trí Position1: có 3 đối tượng d1, d2, d3.
+ Ở vị trí 1, so sánh các đối tượng d1, d2, d3 với các vị trí khác trong List1,
tìm ra vị trí chứa cùng các đối tượng ta được:
d1 <=> vị trí Position 1 có LocalScore = 30
d2 <=> vị trí Position 9 có LocalScore = 28
d3 <=> vị trí Position 4 có LocalScore = 30
=> Ta được P1={1,4,9} => vị trí tốt nhất trong L1 là bp1 = 1
Vị trí tiếp theo trong P1 là 4=> các vị trí 2 và 3 không nhìn thấy.

+ So sánh tiếp các đối tượng d1, d2, d3 với các vị trí khác trong L2, L3, tìm
ra vị trí chứa cùng các đối tượng, ta được:
P2 ={1,6,8} => vị trí tốt nhất trong L2 là bp2 = 1
P3={1,5,8} => vị trí tốt nhất trong L3 là bp3 = 1
14


* Vị trí tốt nhất là vị trí được nhìn thấy gần nhất trước điểm mù.
=> Tính ngưỡng như sau:
N= ∑{ bp1(1),bp2(1),bp3(1)}=30+28+30=88
=> Thiết lập được 3 vùng điểm cao nhất Y= {d1,d2,d3}
Xét theo tổng điểm của mỗi đối tượng và so sánh với N, không thấy có đối
tượng nào lớn hơn hoặc bằng N => BPA tiếp tục thuật toán.
- Xét tại vị trí Position 2, BPA nhìn thấy các đối tượng: d4, d5, d6
+ Tương tự so sánh d1, d2, d3, d4, d5, d6 lần lượt với List1, List2, List3 ta
được:
P1={1, 2, 4, 7, 8, 9},P2={1, 2, 4, 6, 8, 9} và P3={1, 2, 4, 5, 6, 8}
=> ta có bp1=2, bp2=2 và bp3=2
=> Tính ngưỡng như sau:
N = ∑(bp1(2), bp2(2), bp3(2)) = 28 + 27 + 29 = 84
=> Thiết lập được 3 vùng điểm cao nhất Y={ d3, d4,d5}
Xét theo tổng điểm của mỗi đối tượng và so sánh với N, không thấy có đối
tượng nào lớn hơn hoặc bằng N => BPA tiếp tục thuật toán.
- Xét tại vị trí Position 3, BPA nhìn thấy các đối tượng: d7, d8, và d9
+ Tương tự so sánh d1, d2, d3, d4, d5, d6, d7, d8, d9 lần lượt với List1,
List2, List3 ta được:
P1 = P2 ={1, 2, 3, 4, 5, 6, 7, 8, 9}, và P3 ={1, 2, 3, 4, 5, 6, 8, 9,
10}
=> Ta có: bp1=9, bp2=9 và bp3=6
=> Tính ngưỡng như sau:

N = ∑(bp1(9), bp2(9), vp3(6)) = 11 + 13 + 19 = 43

15


=> Thiết lập được 3 vùng điểm cao nhất Y={ d3, d5, d8}
Xét theo tổng điểm của mỗi đối tượng và so sánh với N, ta thấy có đối
tượng lớn hơn hoặc bằng N => BPA dừng.


BPA dừng vị trí Position3

=> Top 2 cần tìm là: d3, d8
2.4. Thuật toán TPUT(Three Phase Uniform Threshold)
Tư tưởng thuật toán: Thuật toán TPUT[3] thực hiện theo 3 pha, pha 1 là duyệt k
hàng trên m danh sách đã được sắp xếp kết quả. Tính tổng điểm mỗi đối tượng trên
k hàng đó. Sau đó sắp xếp lại danh sách tổng điểm để đưa vào danh sách kết quả k
đối tượng có tổng điểm lớn nhất. Pha 2: trong danh sách kết quả vừa thu được ta lại
lấy đối tượng có tổng điểm nhỏ nhất và chia cho tổng số danh sách đầu vào để được
giá trị ngưỡng. Sau đó so sánh điểm mỗi đối tượng trên từng hàng với giá trị
ngưỡng để đưa ra danh sách kết quả thỏa mãn điều kiện lớn hơn hoặc bằng ngưỡng.
Sau khi đưa được ra danh sách kết quả thỏa mãn ta thực hiện tính tổng điểm mỗi đối
tượng đó. Pha 3: Sắp xếp lại danh sách tổng điểm mỗi đối tượng và đưa ra k đối
tượng có tổng điểm lớn nhất.
a. Các bước xây dựng thuật toán TPUT[3]
Pha 1:
- Duyệt các đối tượng trên k hàng đầu tiên, với k thuộc số kết quả trong yêu
cầu top-k ban đầu.
- Tính tổng điểm các đối tượng trên k hàng đầu này theo công thức:
GlobalScore(Oj) = ∑( LocalScorei(Oj)), với i=1..m (m là số danh sách đầu

vào), j=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Oj: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorei(Oj): điểm của đối tượng Oj.

16


+ GlobalScore(Oj): điểm tổng thể của đối tượng Oj.
- So sánh tổng điểm của các đối tượng, đưa ra k bản ghi có tổng điểm cao
nhất vào danh sách Y.
Pha 2:
Trong danh sách Y lấy đối tượng có tổng điểm nhỏ nhất, ký hiệu là t.
+ Tính ngưỡng T theo công thức: t / m, với m là tổng số danh sách đầu vào.
+ Duyệt trên mỗi danh sách và so sánh điểm của mỗi đối tượng với
Ngưỡng.
.Nếu điểm của đối tượng nào thỏa mãn lớn hơn hoặc bằng ngưỡng thì cho
vào danh sách M.
+ Tính tổng điểm của mỗi đối tượng trong danh sách M theo công thức:
GlobalScore(Ot) = ∑( LocalScorel(Ot)), với l=1..m (m là số danh sách đầu
vào), t=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Ot: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorel(Ot): điểm của đối tượng Ot
+ GlobalScore(Ot): điểm tổng thể của đối tượng Ot.
Pha 3: So sánh tổng điểm của mỗi đối tượng trong danh sách M với nhau.
Sắp xếp lại danh sách M, trả ra k kết quả thỏa mãn theo yêu cầu.
b. Ví dụ 5: Cho 3 hệ thống con: subsystem1, subsystem2, subsystem3. Yêu cầu tìm
và đưa ra top-2 đối tượng.


17


Pha 1:
Duyệt 2 vị trí đầu tiên 1 và 2 của cả 3 subsystem.
+ Tại sao lại chỉ chọn vị trí 1 và 2 đầu tiên: vì duyệt qua lần lượt các danh
sách ở từng vị trí, lấy k=2 nên xét 2 vị trí 1 và 2 (Nếu chọn k=3 thì xét vị trí 1,2,3)..
+ Tính tổng điểm mỗi đối tượng:
∑(O5) = 21
∑(O4) = 34+14 = 48
∑(O3) = 30
∑(O2) = 17
∑(O1) = 29


Dựa vào tổng điểm các đối tượng này ta có top k=2 và 2 đối tượng có

tổng điểm cao nhất là Ssum(O4) và Ssum (O3)
=> Pha 1 có Ssum (O3) là giá trị có tổng điểm nhỏ nhất. Ngưỡng sử dụng ở
pha 2 sẽ được tính như sau:

18


N = 30/3=10.
Tại sao lại là chia 3: vì 3 là giá trị trung bình cho 3 danh sách. Nếu có 4
danh sách thì ngưỡng bằng 30 chia 4)
Pha 2:
Tiến hành so sánh các giá trị ở mỗi danh sách cho giá trị ngưỡng, ta lấy các
giá trị xấp xỉ bằng và lớn hơn giá trị ngưỡng.

- Trong danh sách SubSyStem1: lấy giá trị từ vị trí 6 trở lên
- Trong danh sách SubSyStem2: lấy giá trị từ vị trí 4 trở lên
- Trong danh sách SubSyStem3: lấy giá trị từ vị trí 2 trở lên
O3: 67
O4: 59
O0: 29
O1: 29
O5:21
O2: 17
O6: 10
O7: 10

-

Tính tổng điểm của mỗi đối tượng sau khi đưa ra danh sách kết quả so

sánh với ngưỡng: Ta thấy O3 và O4 vẫn thuộc top-2 đối tượng có tổng điểm lớn
nhất:
∑(O3 ) = 67

19


∑ (O4 ) = 59
Y = {O4; O3}
Pha 3:
So sánh tổng điểm của mỗi đối tượng tại Pha 2. Nếu không có đối tượng
nào có giá trị lớn hơn giá trị của O4 hoặc O3 thì dừng.
Kết luận O4, O3 là top-2 đối tượng cần tìm.
2.5. Thuật toán TPAT(Three-Phase Adaptive-Threshold)

Tư tưởng thuật toán: Thuật toán TPAT[3] thực hiện theo 3 pha, pha 1 là duyệt k
hàng trên m danh sách đã được sắp xếp kết quả. Tính tổng điểm mỗi đối tượng trên
k hàng đó. Sau đó sắp xếp lại danh sách tổng điểm để đưa vào danh sách kết quả k
đối tượng có tổng điểm lớn nhất. Pha 2: trong danh sách kết quả vừa thu được ta lại
lấy đối tượng có tổng điểm nhỏ nhất và chia cho tổng số danh sách đầu vào để được
giá trị ngưỡng. Xác định ngưỡng cận trên và ngưỡng cận dưới. Sau đó so sánh điểm
mỗi đối tượng trên từng hàng với các giá trị ngưỡng tương ứng để đưa ra danh sách
kết quả thỏa mãn điều kiện lớn hơn hoặc bằng ngưỡng. Sau khi đưa được ra danh
sách kết quả thỏa mãn ta thực hiện tính tổng điểm mỗi đối tượng đó. Pha 3: Sắp xếp
lại danh sách tổng điểm mỗi đối tượng và đưa ra k đối tượng có tổng điểm lớn nhất.
a. Kỹ thuật xử lý
Pha 1: - Duyệt các đối tượng trên k hàng đầu tiên, với k thuộc số kết quả
trong yêu cầu top-k ban đầu.
- Tính tổng điểm các đối tượng trên k hàng đầu này theo công thức:
GlobalScore(Oj) = ∑( LocalScorei(Oj)), với i=1..m (m là số danh sách đầu
vào), j=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Oj: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorei(Oj): điểm của đối tượng Oj.

20


+ GlobalScore(Oj): điểm tổng thể của đối tượng Oj.
- So sánh tổng điểm của các đối tượng, đưa ra k bản ghi có tổng điểm cao
nhất vào danh sách Y.
Pha 2: Trong danh sách Y lấy đối tượng có tổng điểm nhỏ nhất, ký hiệu là t.
+ Tính giá trị Ngưỡng và lấy các giá trị ngưỡng cận trên và ngưỡng cận
dưới
+ So sánh Ngưỡng, ngưỡng cận trên và ngưỡng cận dưới với điểm của mỗi

đối tượng trong mỗi danh sách tương ứng. Được danh sách M.
+ Tính tổng điểm mỗi đối tượng trong danh sách M theo công thức:
GlobalScore(Ot) = ∑( LocalScorel(Ot)), với l=1..m (m là số danh sách đầu
vào), t=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Ot: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorel(Ot): điểm của đối tượng Ot
+ GlobalScore(Ot): điểm tổng thể của đối tượng Ot.
Pha 3: So sánh tổng điểm của mỗi đối tượng trong danh sách M với nhau.
Sắp xếp lại danh sách M, trả ra k kết quả thỏa mãn theo yêu cầu.
b. Ví dụ 7: Cho ba hệ thống con: subsystem1, subsystem2, subsystem3. Yêu cầu
tìm và đưa ra top-2 đối tượng.

21


Pha 1:
Duyệt 2 vị trí đầu tiên 1 và 2 của cả 3 subsystem.
+ Tại sao lại chỉ chọn vị trí 1 và 2 đầu tiên: vì duyệt qua lần lượt các note ở
từng vị trí, lấy k=2 nên xét 2 vị trí 1 và 2 (Nếu chọn k=3 thì xét vị trí 1,2,3)..
+ Tính tổng mỗi đối tượng:
∑(O5) = 21
∑(O4) = 34+14 = 48
∑(O3) = 30
∑(O2) = 17
∑(O1) = 29


Dựa vào tổng các đối tượng này ta có top k=2 và 2 đối tượng có tổng


điểm cao nhất là Ssum(O4) và Ssum (O3)
=> Pha 1, đối tượng có tổng điểm nhỏ nhất là (O3)
=>> Ngưỡng sử dụng ở pha 2 được tính như sau:

22


N = 30/3=10.
Tại sao lại là chia 3: vì 3 là giá trị trung bình cho 3 danh sách. Nếu có 4
danh sách thì ngưỡng bằng 30 chia 4)…
=>T=10 (mặc định T3 = 10, vì có 3 danh sách (subsystem))
Xác định cận trên và cận dưới ngưỡng, sao cho thỏa mãn giá trị ngưỡng ở
giữa, trong khoảng: >=T>=
- Dựa vào top-k =2, có 3 subsytem=> cận trên, cận dưới chia đều sang 2
bên chênh nhau so với giá trị Ngưỡng 2 đơn vị.
Ta có T1=12>=T3=10>=T2=8
Pha 2:
Tiến hành so sánh các giá trị ở mỗi danh sách cho mỗi giá trị ngưỡng T1,
T2, T3 tương ứng, ta lấy các giá trị xấp xỉ bằng và lớn hơn các giá trị ngưỡng đó.
- Trong danh sách SubSyStem1: lấy giá trị từ vị trí 2 trở lên
- Trong danh sách SubSyStem2: lấy giá trị từ vị trí 5 trở lên
- Trong danh sách SubSyStem3: lấy giá trị từ vị trí 2 trở lên
O3: 56
O4: 48
O5: 30
O0: 29
O1: 29
O2: 17
- Tính tổng mỗi đối tượng (sau khi đưa ra 3 danh sách kết quả): Ta thấy O3
và O4 vẫn thuộc top-2 đối tượng có tổng điểm lớn nhất.

23


∑(O3 ) = 67
∑(O4 ) = 59
Y = {O4; O3}
Pha 3:
So sánh tổng điểm của mỗi đối tượng thuộc Pha 2 với O4, O3. Nếu không
có đối tượng nào có giá trị lớn hơn giá trị của O4 hoặc O3 thì dừng.
Kết luận O4, O3 là top-2 đối tượng cần tìm.
2.6. Thuật toán TPOR(Three-Phase Object-Ranking)
Tư tưởng thuật toán: Thuật toán TPOR[3] thực hiện theo 3 pha, pha 1 là duyệt k
hàng trên m danh sách đã được sắp xếp kết quả. Tính tổng điểm mỗi đối tượng trên
k hàng đó. Sau đó sắp xếp lại danh sách tổng điểm để đưa vào danh sách kết quả k
đối tượng có tổng điểm lớn nhất. Pha 2: trong danh sách kết quả vừa thu được ta lại
lấy đối tượng có tổng điểm nhỏ nhất và chia cho tổng số danh sách đầu vào để được
giá trị ngưỡng. Sau đó so sánh điểm mỗi đối tượng trên từng hàng với giá trị
ngưỡng để đưa ra danh sách kết quả thỏa mãn điều kiện lớn hơn ngưỡng. Sau khi
đưa được ra danh sách kết quả thỏa mãn ta thực hiện tính tổng điểm mỗi đối tượng
đó. Pha 3: Sắp xếp lại danh sách tổng điểm mỗi đối tượng và đưa ra k đối tượng có
tổng điểm lớn nhất.
a. Kỹ thuật xử lý
Pha 1:
- Duyệt các đối tượng trên k hàng đầu tiên, với k thuộc số kết quả trong yêu
cầu top-k ban đầu.
- Tính tổng điểm các đối tượng trên k hàng đầu này theo công thức:
GlobalScore(Oj) = ∑( LocalScorei(Oj)), với i=1..m (m là số danh sách đầu
vào), j=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)

24



+ Oj: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorei(Oj): điểm của đối tượng Oj.
+ GlobalScore(Oj): điểm tổng thể của đối tượng Oj.
- So sánh tổng điểm của các đối tượng, đưa ra k bản ghi có tổng điểm cao
nhất vào danh sách Y.
Pha 2:
Trong danh sách Y lấy đối tượng có tổng điểm nhỏ nhất, ký hiệu là t.
+ Tính ngưỡng T theo công thức: t / m, với m là tổng số danh sách đầu vào.
+ Duyệt trên mỗi danh sách và so sánh điểm của mỗi đối tượng với
Ngưỡng.
.Nếu điểm của đối tượng nào thỏa mãn lớn hơn hoặc bằng ngưỡng thì cho
vào danh sách M.
+ Tính tổng điểm của mỗi đối tượng trong danh sách M theo công thức:
GlobalScore(Ot) = ∑( LocalScorel(Ot)), với l=1..m (m là số danh sách đầu
vào), t=1..n (n là số đối tượng trên m danh sách, n>0, n ∈ N)
+ Ot: Đối tượng được tìm thấy sớm nhất qua mỗi lần duyệt trên từng hàng
của mỗi danh sách.
+ LocalScorel(Ot): điểm của đối tượng Ot
+ GlobalScore(Ot): điểm tổng thể của đối tượng Ot.
Pha 3: So sánh tổng điểm của mỗi đối tượng trong danh sách M với nhau.
Sắp xếp lại danh sách M, trả ra k kết quả thỏa mãn theo yêu cầu.
b. Ví dụ 10: Cho 3 hệ thống con: subsystem1, subsystem2, subsystem3. Yêu cầu
tìm và đưa ra top-2 đối tượng.

25