關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢結(jié)果排序方法

王瑛琦， 周連科， 王念濱

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

隨著關(guān)系數(shù)據(jù)庫(kù)中信息量的快速增長(zhǎng)，訪問(wèn)、查詢關(guān)系數(shù)據(jù)庫(kù)成為人們獲取信息的重要途徑之一[1]。關(guān)鍵字查詢以其簡(jiǎn)單易用的特點(diǎn)受到廣泛關(guān)注，相比于傳統(tǒng)的結(jié)構(gòu)化查詢方法(如SQL查詢)，該方法不需要用戶了解復(fù)雜的查詢語(yǔ)言和數(shù)據(jù)庫(kù)底層模式，為用戶查詢帶來(lái)諸多便利[2-3]。然而，關(guān)鍵字查詢作為一種模糊查詢方法，并不能精確地鎖定數(shù)據(jù)庫(kù)中與用戶需求最相關(guān)的信息，而是將包含查詢?cè)~的所有元組(元組單元)返回給用戶。用戶需要在大量查詢結(jié)果中進(jìn)一步篩選出自己所需要的信息。因此，按照重要性及相關(guān)性對(duì)查詢結(jié)果進(jìn)行排序顯得尤為重要，成為關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢領(lǐng)域的重要組成部分和研究熱點(diǎn)之一[4]。

近年來(lái)，一些學(xué)者已經(jīng)對(duì)該領(lǐng)域進(jìn)行初步研究，并提出多種關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢結(jié)果排序方法。例如，Vagelis Hristidis等[5]提出一種簡(jiǎn)單且直接的排序方法，根據(jù)查詢結(jié)果所包含的元組數(shù)對(duì)結(jié)果進(jìn)行排序。該方法雖然簡(jiǎn)單但排序準(zhǔn)確率較低。Liu Fang等[6]在此基礎(chǔ)上將信息檢索中成熟的相關(guān)性排序機(jī)制引入關(guān)系數(shù)據(jù)庫(kù)中，進(jìn)一步提高排序準(zhǔn)確率。然而，隨著排序結(jié)果的影響因素不斷增多，排序函數(shù)日趨復(fù)雜。關(guān)于影響因子權(quán)重的調(diào)節(jié)缺少一種理論化指導(dǎo)方案，需要在大量實(shí)驗(yàn)和經(jīng)驗(yàn)積累的基礎(chǔ)上手動(dòng)進(jìn)行設(shè)置。因此，排序模型的準(zhǔn)確率受到人為因素和實(shí)驗(yàn)環(huán)境等外界條件的影響。與此同時(shí)，學(xué)習(xí)排序作為一種新興排序方法在信息檢索和機(jī)器學(xué)習(xí)領(lǐng)域得到了廣泛應(yīng)用[7]。該方法基于訓(xùn)練數(shù)據(jù)集，使用機(jī)器學(xué)習(xí)算法自動(dòng)化排序過(guò)程。相對(duì)于傳統(tǒng)排序方法而言，該方法避免了定義排序函數(shù)所需要的人力勞動(dòng)并使排序模型在效率和準(zhǔn)確率方面均有顯著提高。受到信息檢索中學(xué)習(xí)排序方法的啟發(fā)，Joel Coffman等[8]將學(xué)習(xí)排序方法SVM Rank應(yīng)用到關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢結(jié)果排序領(lǐng)域。然而，該方法也存在較為突出的問(wèn)題。首先，SVM Rank是一種典型的虛擬文檔對(duì)級(jí)排序方法[9]，并未考慮到排序是對(duì)一列虛擬文檔的預(yù)測(cè)工作；其次，當(dāng)面對(duì)海量訓(xùn)練數(shù)據(jù)時(shí)，該方法的訓(xùn)練過(guò)程需要大量時(shí)間開(kāi)銷。因此算法的效率和準(zhǔn)確率均存在較大的提升空間[10]。

在上述研究的基礎(chǔ)上，本文將學(xué)習(xí)排序模型引入關(guān)系數(shù)據(jù)庫(kù)領(lǐng)域，并作進(jìn)一步的改進(jìn)與完善，提出一種基于虛擬文檔列表的并行學(xué)習(xí)排序方法Parallel AdaRdbRank-Hierarchy(PARR-H)用以解決關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢結(jié)果的排序問(wèn)題。

1 基于虛擬文檔列表的學(xué)習(xí)排序算法

算法ARR-H是一種虛擬文檔列表級(jí)的學(xué)習(xí)排序算法，與文獻(xiàn)[8]中基于虛擬文檔對(duì)的算法相比，該算法充分考慮虛擬文檔間的序列關(guān)系并直接對(duì)虛擬文檔列表進(jìn)行優(yōu)化，因此在排序模型的準(zhǔn)確率方面有了較大提高。另外，該算法使用分層的弱排序器構(gòu)建策略：首先，根據(jù)特征的重要性及特征間的相似性，使用貪婪算法構(gòu)建候選弱排序器集合Sk；其次，根據(jù)候選弱排序器的排序性能從集合Sk中選取得分最高的候選弱排序器作為本次迭代的弱排序器。使用以上分層思想構(gòu)建弱排序器，能夠有效地避免冗余弱排序器的產(chǎn)生。具體實(shí)現(xiàn)如算法1所示。

算法1ARR-H

輸出：f(x)=fT(x)；

步驟：

1)初始化D(i)=1/n，S0=φ；

5)Fori=1 tokdo

7)E(xj)←E(xj)-A(xgxj)*2c，j≠g

8)Si=Si-1∪{xg}，Gi=Gi-1{xg}；

9)EndFor

10)Fort=1 toTdo

11)計(jì)算

13)選擇?t

14)

15)構(gòu)建ft

17)更新D(t+1)

18)

19)EndFor

20)輸出排序模型：f(x)=fT(x)；

算法ARR-H采用虛擬文檔列表級(jí)的學(xué)習(xí)排序思想，同時(shí)結(jié)合分層弱排序器構(gòu)建策略，初步解決了關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢結(jié)果的排序問(wèn)題。然而，隨著訓(xùn)練樣本規(guī)模的不斷擴(kuò)大，該算法的訓(xùn)練效率面臨嚴(yán)峻挑戰(zhàn)，需要對(duì)以上算法作進(jìn)一步改進(jìn)，以提高算法的效率。因此，提出并行學(xué)習(xí)排序算法PARR-H。

2 并行學(xué)習(xí)排序算法

在算法ARR-H的基礎(chǔ)上，加入并行框架如圖1所示。

圖1 并行學(xué)習(xí)排序架構(gòu)圖Fig.1 Architecture of the parallel learning-to-rank

假設(shè)有K個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)并行地在各自的局部數(shù)據(jù)上訓(xùn)練局部弱排序器并計(jì)算所需要的信息。中心節(jié)點(diǎn)收集所有節(jié)點(diǎn)上的信息，并進(jìn)行統(tǒng)計(jì)綜合，得到整體弱排序器。中心節(jié)點(diǎn)將得到的排序模型返回給每個(gè)子節(jié)點(diǎn)，子節(jié)點(diǎn)使用此排序模型進(jìn)行訓(xùn)練以得到下次迭代所需要的信息。經(jīng)過(guò)T次循環(huán)后，得到最終的排序公式f，當(dāng)新數(shù)據(jù)到來(lái)時(shí)使用公式f對(duì)其進(jìn)行排序得到排序結(jié)果。由于訓(xùn)練實(shí)例分布在K個(gè)節(jié)點(diǎn)上同時(shí)進(jìn)行訓(xùn)練，使得訓(xùn)練效率有了顯著提高。具體實(shí)現(xiàn)見(jiàn)算法2。

算法2PARR-H

輸出：f(x)=fT(x)；

步驟：

1)初始化D1(i)=1/nK；

2)調(diào)用算法3并行構(gòu)建候選弱排序器集Sk；

3)Fort=1 toTdo

4)Forj=1 toK(in parallel) do

5)計(jì)算

6)EndFor

9)選擇?t

11)創(chuàng)建ft

13)Forj=1 toK(in parallel) do

14)更新D(t+1),j

15)D(t+1),j(i)=

16)EndFor

17)更新D(t+1)

18)

19)EndFor

20)輸出排序模型：f(x)=fT(x)；

在算法2中，數(shù)據(jù)被隨機(jī)分布在K個(gè)節(jié)點(diǎn)上，這樣訓(xùn)練任務(wù)可并發(fā)執(zhí)行，從而減少訓(xùn)練的時(shí)間開(kāi)銷；2)步調(diào)用算法3并行地構(gòu)建候選弱排序器集合Sk，包含k個(gè)候選弱排序器，其詳細(xì)的實(shí)現(xiàn)過(guò)程將在第3節(jié)算法3中具體介紹；3)～6)步在子節(jié)點(diǎn)上并行計(jì)算候選弱排序器的局部重要性，并將此信息發(fā)送給中心節(jié)點(diǎn)；7)～8)步中心節(jié)點(diǎn)整合從子節(jié)點(diǎn)獲得的所有信息，構(gòu)建此次迭代的整體弱排序器；9)～12)步根據(jù)整體弱排序器的排序性能E計(jì)算弱排序器的權(quán)重，并將其加入現(xiàn)有的排序模型；13)～16)步，中心節(jié)點(diǎn)將此次迭代后形成的排序模型返回到每個(gè)子節(jié)點(diǎn)，子節(jié)點(diǎn)根據(jù)此排序模型對(duì)訓(xùn)練實(shí)例的局部權(quán)重分布進(jìn)行更新；17)～18)步對(duì)訓(xùn)練實(shí)例的全局權(quán)重分布進(jìn)行更新；經(jīng)過(guò)T次循環(huán)，最終得到排序模型f(x)=fT(x)。算法1)步的時(shí)間復(fù)雜度為O(n)；2)步的時(shí)間復(fù)雜度為O(n+m2)；3)～19)步的時(shí)間復(fù)雜度為O((m+n)T)；因此算法2的時(shí)間復(fù)雜度為O(nT+m2)，其中n為子節(jié)點(diǎn)上的訓(xùn)練實(shí)例數(shù)，T為循環(huán)次數(shù)，m為特征總數(shù)。

3 弱排序器分層構(gòu)建策略

通過(guò)對(duì)算法PARR-H的分析可知，經(jīng)過(guò)T次循環(huán)，該算法最終輸出的排序模型f(x)=fT(x)是多個(gè)弱排序器及其權(quán)重的線性組合。而在每次循環(huán)中，弱排序器的選擇直接影響了訓(xùn)練效率和排序模型的有效性。因此，本節(jié)將會(huì)對(duì)弱排序器的構(gòu)建進(jìn)行深入研究，并提出一種基于貪婪算法和整體排序性能的分層構(gòu)建策略。該策略既能保證較高的排序性能，同時(shí)可有效避免冗余排序器的產(chǎn)生。分為兩個(gè)階段：1)構(gòu)建候選弱排序集合Sk；2)根據(jù)弱排序器的排序性能，從集合Sk中進(jìn)一步選擇每次循環(huán)中的弱排序器。在階段1中，子節(jié)點(diǎn)并行地計(jì)算特征的局部重要性和局部相似性。并將其傳送給中心節(jié)點(diǎn)，中心節(jié)點(diǎn)整合以上信息得到每個(gè)特征的全局重要性及特征間的全局相似性。以特征為頂點(diǎn)，全局重要性為節(jié)點(diǎn)權(quán)重，全局相似性為邊權(quán)重構(gòu)建全局特征關(guān)聯(lián)圖G0。使用貪婪算法在圖G0上進(jìn)行搜索得到候選弱排序器集合Sk。特征的全局重要性和全局相似性計(jì)算過(guò)程如下：

1)特征的全局重要性。

2)特征的全局相似性。

將每個(gè)特征作為一個(gè)排序模型，并由此得到不同的排序結(jié)果。使用排序結(jié)果間的相似性作為特征間的相似性，本文選取皮爾森相關(guān)系數(shù)對(duì)排序結(jié)果相似性進(jìn)行度量。相似性的計(jì)算：

Al,j(xkxf)=

(1)

式中：xk和xf為任意兩個(gè)不同的特征，K為節(jié)點(diǎn)數(shù)，Al,j(xkxf)表示在節(jié)點(diǎn)j上特征xk和xf間的局部相似性，Ag(xkxf)表示在K個(gè)節(jié)點(diǎn)上特征xk和xf間的全局相似性。cov(vdxk,vdxf)為根據(jù)特征xk和xf所得排序結(jié)果的協(xié)方差，var(vdxk)為根據(jù)特征xk所得排序結(jié)果的方差。

算法3PCAWR(parallel construction algorithm of candidate weak rankersSk)

輸入：K，Dj，k，c；

輸出：候選弱排序器集Sk；

步驟：

1)初始化Dj=1/n(每個(gè)節(jié)點(diǎn)包含n個(gè)實(shí)例)，S0=φ；

2)Forj=1 toK(in parallel) do

4)得到

5)EndFor

6)計(jì)算

；

8)Fori=1 tokdo

9)對(duì)Eg(xM)降序排序，xg←argmaxEg(xM)；

10)Eg(xj)←Eg(xj)-Ag(xgxj)*2c，j≠g

11)Si=Si-1∪{xg}，Gi=Gi-1{xg}；

12)EndFor

13)輸出Sk

算法3描述了弱排序器構(gòu)建的第一階段：并行構(gòu)建候選弱排序器集合Sk。算法1)步初始化，分別為每個(gè)節(jié)點(diǎn)上的訓(xùn)練實(shí)例賦予相同的權(quán)重分布，初始化候選弱排序器集合S0=φ；2)～5)步在每個(gè)子節(jié)點(diǎn)上并行地計(jì)算特征的局部重要性和特征間的局部相似性，并將結(jié)果返回給中心節(jié)點(diǎn)；6)～7)步中心節(jié)點(diǎn)計(jì)算特征的全局重要性和全局相似性，進(jìn)而構(gòu)建全局特征關(guān)聯(lián)圖G0；8)～12)步選擇全局重要性最大的特征，將其加入候選弱排序器集合S，并對(duì)特征全局關(guān)聯(lián)圖進(jìn)行更新。k次循環(huán)后得到包含k個(gè)特征的候選弱排序集合Sk。算法1)步的時(shí)間復(fù)雜度為O(n)；第2～5步的時(shí)間復(fù)雜度為O(m)+O(m(m-1)/2)；6)～7)步的時(shí)間復(fù)雜度為O(m)+O(m(m-1)/2)；8)～12)步的時(shí)間復(fù)雜度為O(k·m)。綜上所述算法3的時(shí)間復(fù)雜度O(n+m2)，其中n為子節(jié)點(diǎn)上的訓(xùn)練實(shí)例數(shù)，m為特征總數(shù)。

4 實(shí)驗(yàn)結(jié)果與分析

在數(shù)據(jù)集IMDB[11]和Wikipedia[12]上進(jìn)行實(shí)驗(yàn)，通過(guò)與基準(zhǔn)方法SVM Rank進(jìn)行比較分析，驗(yàn)證算法ARR-H和PARR-H的有效性和效率。選擇SVM Rank算法作為基準(zhǔn)方法，因?yàn)樵撍惴ㄊ顷P(guān)系數(shù)據(jù)庫(kù)領(lǐng)域中最為經(jīng)典的學(xué)習(xí)排序方法，并且Joel Coffman等[8]已經(jīng)通過(guò)多組對(duì)比實(shí)驗(yàn)驗(yàn)證了該學(xué)習(xí)排序方法在排序準(zhǔn)確率方面優(yōu)于傳統(tǒng)的信息檢索式排序方法。

4.1 實(shí)驗(yàn)設(shè)置

分別抽取原始數(shù)據(jù)集IMDB和Wikipedia的子集作為本次實(shí)驗(yàn)的數(shù)據(jù)集。表1記錄了關(guān)于該數(shù)據(jù)集的統(tǒng)計(jì)結(jié)果。另外，實(shí)驗(yàn)包括1個(gè)主節(jié)點(diǎn)和4個(gè)子節(jié)點(diǎn)。其中每個(gè)節(jié)點(diǎn)的配置為Intel(R)Core(TM)i5-4570 CPU 3.20 GHz，內(nèi)存容量4G，硬盤(pán)容量1 TB，操作系統(tǒng)WIN 10(64 bit)。在進(jìn)行實(shí)驗(yàn)之前，需要對(duì)原始數(shù)據(jù)集進(jìn)行預(yù)處理。分別在數(shù)據(jù)集IMDB和Wikipedia上隨機(jī)生成250個(gè)查詢，基于三個(gè)系統(tǒng)BANKS、DISCOVER、SPARK得到與查詢相關(guān)聯(lián)的查詢結(jié)果，這里統(tǒng)稱為虛擬文檔。針對(duì)每個(gè)查詢，從3個(gè)系統(tǒng)返回的結(jié)果中選取top-100虛擬文檔放入數(shù)據(jù)池，并由此產(chǎn)生實(shí)驗(yàn)所需的訓(xùn)練實(shí)例。使用五折交叉驗(yàn)證實(shí)驗(yàn)減小評(píng)分函數(shù)過(guò)擬合的風(fēng)險(xiǎn)。將數(shù)據(jù)池中的數(shù)據(jù)隨機(jī)分為5個(gè)子集合，每個(gè)子集合包含50個(gè)查詢及其對(duì)應(yīng)的虛擬文檔。其中4個(gè)子集合用于訓(xùn)練，剩余1個(gè)子集合用于測(cè)試。注意，在算法PARR-H執(zhí)行過(guò)程中，訓(xùn)練集的4個(gè)子集合被分布在4個(gè)子節(jié)點(diǎn)上，主節(jié)點(diǎn)使用測(cè)試集對(duì)訓(xùn)練結(jié)果進(jìn)行測(cè)試。表2和表3分別顯示實(shí)驗(yàn)中的查詢劃分以及五折交叉驗(yàn)證中的數(shù)據(jù)集劃分，其中QID為查詢ID號(hào)。

表1 實(shí)驗(yàn)數(shù)據(jù)集

表2 查詢劃分

表3 交叉驗(yàn)證的數(shù)據(jù)集劃分

4.2 有效性

使用MAP和NDCG兩種度量指標(biāo)作為排序模型的效果評(píng)估標(biāo)準(zhǔn)。給定查詢q，第i位上的NDCG值計(jì)算如下

式中：r(j)為第j位虛擬文檔的相關(guān)度等級(jí)，ni為歸一化因子。

查詢q的平均準(zhǔn)確率計(jì)算如下：

式中：P(j)為排在前j位虛擬文檔的查準(zhǔn)率；pos(j)為二值函數(shù)，當(dāng)?shù)趈位虛擬文檔為相關(guān)文檔時(shí)pos(j)=1，反之pos(j)=0；N為通過(guò)查詢q返回的虛擬文檔數(shù);Nq為查詢q相關(guān)的虛擬文檔數(shù)。多個(gè)查詢的AP值取平均即可得到MAP值。

4.2.1 數(shù)據(jù)集IMDB上的實(shí)驗(yàn)

本節(jié)使用數(shù)據(jù)集IMDB驗(yàn)證算法ARR-H和PARR-H的性能。這里，將算法SVM Rank記為‘SVM-R’。圖2中x軸為虛擬文檔在文檔序列中所在的位置，y軸為三種排序算法在各個(gè)位置上所對(duì)應(yīng)的NDCG@n值。由圖2可知，算法ARR-H和PARR-H在NDCG@n上均優(yōu)于算法SVM-R。具體來(lái)講，當(dāng)n=1時(shí)相對(duì)于SVM-R，ARR-H和PARR-H分別提高13.3%和8.2%。而關(guān)于NDCG@5，ARR-H和PARR-H相對(duì)于SVM-R分別提高9.1%和7.0%。另外，在該實(shí)驗(yàn)中算法SVM-R的MAP值為0.309，而ARR-H和PARR-H的MAP值分別為0.335、0.317，相對(duì)于SVM-R分別提高約8.4%和2.6%。產(chǎn)生上述實(shí)驗(yàn)結(jié)果的原因是：本文提出的算法ARR-H和PARR-H為虛擬文檔列級(jí)的學(xué)習(xí)排序方法，與文檔對(duì)級(jí)的排序方法SVM-R相比，以上兩種方法不再將排序問(wèn)題歸納為二元分類問(wèn)題，而是直接優(yōu)化排序評(píng)價(jià)指標(biāo)，從而提高排序模型的精度。另外，算法ARR-H和PARR-H使用分層式弱排序器構(gòu)建策略IS-BGEM(importance & similarity-based on global evealvation measure)，避免了冗余弱排序器的產(chǎn)生，進(jìn)一步提高了排序模型的精度。而ARR-H的實(shí)驗(yàn)結(jié)果優(yōu)于PARR-H，其主要原因是：將訓(xùn)練數(shù)據(jù)分散在不同節(jié)點(diǎn)上進(jìn)行并行化處理，對(duì)排序模型精度方面造成一定程度的影響，一方面節(jié)點(diǎn)間的數(shù)據(jù)通信降低了模型的可靠性。另一方面，算法中特征的全局重要性和全局相似性以及訓(xùn)練樣本的全局分布，均和實(shí)際單節(jié)點(diǎn)上的算法運(yùn)行有所差異。本文方法在NDCG@1上的提高幅度最為顯著，說(shuō)明該方法適用于Web數(shù)據(jù)庫(kù)，此應(yīng)用環(huán)境強(qiáng)調(diào)位置靠前的結(jié)果。

圖2 數(shù)據(jù)集IMDB上的NDCG@n值Fig.2 Ranking performance NDCG@n on IMDB

4.2.2 數(shù)據(jù)集Wikipedia上的實(shí)驗(yàn)

在數(shù)據(jù)集Wikipedia上同樣進(jìn)行五折交叉驗(yàn)證實(shí)驗(yàn)。由圖3可以看出在數(shù)據(jù)集Wikipedia上的實(shí)驗(yàn)結(jié)果與數(shù)據(jù)集IMDB上的結(jié)果相類似。ARR-H的NDCG@n值優(yōu)于其他兩種排序算法。例如，與SVM-R相比，ARR-H的NDCG@5值提高6.6%，PARR-H的NDCG@5值提高5.2%。另外，SVM-R、ARR-H、PARR-H所對(duì)應(yīng)的MAP值分別為0.443、0.473、0.452。其中，ARR-H的MAP值最大，相比于SVM-R提高6.8%。PARR-H的MAP值相比于SVM-R提高2.0%，而與ARR-H相比，有所降低。

圖3 數(shù)據(jù)集Wikipedia上的NDCG@n值Fig.3 Ranking performance NDCG@n on Wikipedia

4.3 訓(xùn)練效率

圖4給出隨著訓(xùn)練實(shí)例規(guī)模的變化，3種排序算法訓(xùn)練時(shí)間的變化情況。由圖4可知，相對(duì)于另外兩種排序算法，PARR-H的訓(xùn)練時(shí)間明顯減少。當(dāng)訓(xùn)練實(shí)例個(gè)數(shù)為10 000時(shí)，PARR-H的訓(xùn)練時(shí)間為4.9 min，而SVM-R和ARR-H的訓(xùn)練時(shí)間分別為25.5 min和16.1 min。通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的分析可以發(fā)現(xiàn)，隨著訓(xùn)練實(shí)例規(guī)模的不斷增大，PARR-H算法效率提高越明顯。當(dāng)訓(xùn)練實(shí)例的個(gè)數(shù)達(dá)到20 000時(shí)，PARR-H的訓(xùn)練時(shí)間為51.2 min，而SVM-R的訓(xùn)練時(shí)間達(dá)到179.8 min。產(chǎn)生上述實(shí)驗(yàn)結(jié)果主要是由于PARR-H和ARR-H均為列表級(jí)的學(xué)習(xí)排序方法，其訓(xùn)練對(duì)象為查詢相關(guān)的虛擬文檔列表，更接近于實(shí)際意義上的排序操作。而SVM-R為文檔對(duì)級(jí)的學(xué)習(xí)排序方法，其訓(xùn)練對(duì)象為查詢相關(guān)的虛擬文檔對(duì)，排序過(guò)程中著重考慮虛擬文檔對(duì)間的偏序關(guān)系，而未考慮虛擬文檔在整個(gè)文檔列表中的序列關(guān)系。因此，PARR-H和ARR-H在排序性能上有較大提高。而PARR-H為學(xué)習(xí)排序加入并行框架，將訓(xùn)練樣本分布在不同機(jī)器上并行化訓(xùn)練過(guò)程，因此學(xué)習(xí)排序模型的訓(xùn)練效率得到進(jìn)一步提高。

圖4 不同規(guī)模訓(xùn)練實(shí)例下的訓(xùn)練時(shí)間Fig.4 Training time for different numbers of training instances

5 結(jié)論

1)提出一種列表級(jí)的學(xué)習(xí)排序算法ARR-H。該算法充分考慮虛擬文檔間的序列關(guān)系，同時(shí)結(jié)合弱排序器分層構(gòu)建思想，提高排序模型的有效性。

2)構(gòu)建一種并行學(xué)習(xí)排序框架PARR-H，并行化訓(xùn)練過(guò)程，有效解決了面對(duì)大規(guī)模訓(xùn)練實(shí)例時(shí)ARR-H算法訓(xùn)練效率低的問(wèn)題。

3)通過(guò)在數(shù)據(jù)集IMDB和Wikipedia上進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文學(xué)習(xí)排序算法ARR-H和PARR-H在有效性和效率方面均有顯著提高，尤其當(dāng)訓(xùn)練實(shí)例規(guī)模較大時(shí)，PARR-H在訓(xùn)練效率上的優(yōu)勢(shì)更為突出。

在未來(lái)的研究中，將在更大規(guī)模的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證排序算法的可擴(kuò)展性。

[1] TRAN T， ZHANG L. Keyword query routing[J]. IEEE transactions on knowledge and data engineering, 2014, 26(2): 363-375.

[2] ZUZE H, WEIDEMAN M. Keyword stuffing and the big three search engines[J]. Online information review, 2013, 37(2): 268-286.

[3] KARGAR M, AN A, CERCONE N, et al. Meaningful keyword search in relational databases with large and complex schema[C]//Proceeding of 2015 IEEE 31st International Conference on Data Engineering. Seoul, Korea, 2015: 411-422.

[4] PARK J, LEE S G. Keyword search in relational databases[J]. Knowledge and information systems, 2011, 26(2): 175-193.

[5] HRISTIDIS V, PAPAKONSTANTINOU Y. Discover: keyword search in relational databases[C]//Proceeding of the 28th international conference on Very Large Data Bases. Hong Kong, China, 2002: 670-681.

[6] LIU F, YU C, MENG W, et al. Effective keyword search in relational databases[C]//Proceeding of 2006 ACM SIGMOD international conference on Management of data. Chicago, USA, 2006: 563-574.

[7] PAN Y, LUO H X, TANG Y, et al. Learning to rank with document ranks and scores[J]. Knowledge-based systems, 2011, 24(4): 478-483.

[8] COFFMAN J, WEAVER A C. Learning to rank results in relational keyword search[C]//Proceeding of the 20th ACM international conference on Information and knowledge management. Glasgow, United Kingdom, 2011: 1689-1698.

[9] CHAPELLE O, KEERTHI S. Efficient algorithms for ranking with SVMs[J]. Information retrieval, 2010, 13(3): 201-215.

[10] LI H. A short introduction to learning to rank[J]. IEICE Transactions on information and systems, 2011, E94D(10): 1854-1862.

本文引用格式：

王瑛琦， 周連科， 王念濱. 關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵字查詢結(jié)果排序方法[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2017， 38(12): 1937-1942， 1963.

WANG Yingqi, ZHOU Lianke, WANG Nianbin. Research on ranking method for relational databases[J]. Journal of Harbin Engineering University， 2017， 38(12): 1937-1942， 1963.