祝官文, 周連科, 王念濱, 劉丹

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

?

基于查詢意圖的數(shù)據(jù)空間預(yù)取方法

祝官文, 周連科, 王念濱, 劉丹

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

摘要：為在查詢前預(yù)取用戶可能訪問(wèn)的數(shù)據(jù)，提出了一種利用查詢?nèi)罩镜臄?shù)據(jù)空間預(yù)取方法。該方法從查詢?nèi)罩局刑崛∫鈭D特征，并采用聚類技術(shù)對(duì)其進(jìn)行聚類，識(shí)別用戶查詢意圖，并基于該意圖預(yù)取查詢結(jié)果。實(shí)驗(yàn)結(jié)果表明：該方法在預(yù)取準(zhǔn)確率和查詢效率方面均顯著優(yōu)于已有方法。

關(guān)鍵詞：數(shù)據(jù)空間；預(yù)?。徊樵円鈭D；聚類；查詢?nèi)罩荆徊樵兘Y(jié)果；預(yù)取準(zhǔn)確率；查詢效率

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)呈現(xiàn)海量、多樣等特點(diǎn)，面對(duì)這些新的數(shù)據(jù)管理特點(diǎn)，傳統(tǒng)的數(shù)據(jù)管理系統(tǒng)已無(wú)法滿足當(dāng)今用戶的需求，為此，Michael Franklin等[1]提出了一種嶄新的數(shù)據(jù)管理思想——數(shù)據(jù)空間。而正是因?yàn)閿?shù)據(jù)空間的特點(diǎn)[2]，導(dǎo)致了用戶對(duì)數(shù)據(jù)空間的查詢?cè)L問(wèn)產(chǎn)生較大延遲，從而影響了數(shù)據(jù)空間的服務(wù)質(zhì)量。因此研究如何降低數(shù)據(jù)空間的訪問(wèn)延遲，提高數(shù)據(jù)空間管理系統(tǒng)性能具有重大價(jià)值。目前解決網(wǎng)絡(luò)延遲、提高查詢效率的有效方法之一是預(yù)取技術(shù)[3-4]。

目前已有的預(yù)取方法總體上可以分為兩類：一種是對(duì)用戶歷史訪問(wèn)序列進(jìn)行分類總結(jié)，判斷用戶當(dāng)前訪問(wèn)類型，預(yù)測(cè)該用戶最可能訪問(wèn)的數(shù)據(jù)序列，如基于數(shù)據(jù)挖掘的預(yù)取方法(mining-prefetching，MI)、基于Markov模型的預(yù)取方法(Markov-prefetching，MA)等[5-6]；另一種是通過(guò)分析用戶最近訪問(wèn)的數(shù)據(jù)內(nèi)容，根據(jù)內(nèi)容之間的關(guān)聯(lián)，發(fā)現(xiàn)最可能被訪問(wèn)的其它數(shù)據(jù)，如基于流行度的預(yù)取方法[7](popularity-prefetching，PO)、基于神經(jīng)網(wǎng)絡(luò)的預(yù)取方法(NN-prefetching，NN)等[8]。

通過(guò)對(duì)現(xiàn)有的預(yù)取方法進(jìn)行分析發(fā)現(xiàn)，它們主要存在以下問(wèn)題：

1)大多數(shù)預(yù)取方法都是基于Web非結(jié)構(gòu)化數(shù)據(jù)的預(yù)取，僅針對(duì)單一類型數(shù)據(jù)，而沒(méi)有綜合考慮結(jié)構(gòu)化、非結(jié)構(gòu)化等多種異構(gòu)數(shù)據(jù)的統(tǒng)一預(yù)取機(jī)制；

2)除了基于語(yǔ)義的預(yù)取方法，其他預(yù)取方法都不能對(duì)用戶歷史上沒(méi)有訪問(wèn)過(guò)的數(shù)據(jù)進(jìn)行預(yù)取。

3)沒(méi)有考慮用戶查詢意圖，預(yù)取的效果較差。

為此，本文將用戶查詢意圖應(yīng)用到數(shù)據(jù)空間預(yù)取中，提出了一種基于查詢意圖的數(shù)據(jù)空間預(yù)取方法(query intent-prefetching，QI)，以有效解決上述問(wèn)題。其主要思想是：首先提取用戶搜索日志的意圖特征，采用SOM聚類算法將查詢?cè)~相同的用戶搜索日志按照查詢意圖劃分為不同的意圖類，然后識(shí)別用戶當(dāng)前查詢最傾向的意圖類，根據(jù)該意圖類對(duì)用戶可能訪問(wèn)的數(shù)據(jù)進(jìn)行預(yù)測(cè)。

1意圖特征提取

查詢意圖是指在用戶提交某一查詢后，實(shí)際期望瀏覽的數(shù)據(jù)。通常情況下，用戶很難通過(guò)僅提交一次查詢獲得符合其真實(shí)意圖的查詢結(jié)果。在數(shù)據(jù)空間的用戶查詢?nèi)罩局?，每條記錄記載了用戶對(duì)某一實(shí)體對(duì)象的查詢?cè)L問(wèn)信息，用戶連續(xù)訪問(wèn)的實(shí)體對(duì)象可能屬于同一個(gè)查詢意圖，也可能不屬于同一個(gè)查詢意圖。為了便于提取相同查詢?cè)~的不同查詢意圖，本文使用簡(jiǎn)單易行的查詢意圖切分方法，把用戶輸入一個(gè)查詢?cè)~后做出的連續(xù)訪問(wèn)記錄切分為同一個(gè)查詢意圖，若重新輸入新的查詢?cè)~，則將后續(xù)訪問(wèn)記錄切分為另一個(gè)查詢意圖。屬于同一個(gè)查詢意圖的所有日志記錄記為一個(gè)搜索日志。這樣每個(gè)搜索日志中包含一條或者多條日志記錄，每條日志記錄中記載了用戶對(duì)某一實(shí)體的訪問(wèn)信息。

數(shù)據(jù)空間擴(kuò)展倒排列表中記錄了出現(xiàn)在每個(gè)實(shí)體中的關(guān)鍵詞，對(duì)于每個(gè)搜索日志，可根據(jù)擴(kuò)展倒排列表和詞性分析，從實(shí)體中提取出名詞或者專有名詞作為該搜索日志的意圖特征，并采用TF-IDF方法計(jì)算出這些特征在該搜索日志中的權(quán)重，具體定義如下：

(1)

式中：wij表示第i個(gè)特征在第j搜索日志中的權(quán)重，tfij表示第i個(gè)特征在第j個(gè)搜索日志中出現(xiàn)的頻率，max(tfj)表示第j個(gè)搜索日志中所有特征出現(xiàn)頻率的最大值，dfi表示包含第i個(gè)特征的搜索日志數(shù)目，n表示所有搜索日志的數(shù)目。

然而TF-IDF機(jī)制本身僅僅是一種基于頻率信息的特征權(quán)重表示方法，并不能充分體現(xiàn)意圖特征之間、搜索日志之間以及意圖特征和搜索日志之間的語(yǔ)義關(guān)聯(lián)，也因此不能依據(jù)語(yǔ)義信息對(duì)用戶查詢意圖進(jìn)行建模。因此本文引入了LSA(latent semantic analysis)方法對(duì)其分析建模[9]，通過(guò)低秩近似的方法對(duì)搜索日志意圖特征向量進(jìn)行降維操作，將意圖特征向量映射到低維語(yǔ)義空間，以表達(dá)其語(yǔ)義特性。

圖1　SVD分解Fig.1　SVD decompositon

圖1展示了“意圖特征-搜索日志”矩陣進(jìn)行奇異值分解，其中，矩陣X為“意圖特征-搜索日志”矩陣，m表示所提取的全部特征數(shù)，n表示所有的搜索日志數(shù)。通過(guò)SVD分解，得到由矩陣X的左、右奇異向量分別構(gòu)成的矩陣F0和D0，以及由所有奇異值自大到小排列構(gòu)成的對(duì)角陣S0，其中r為矩陣X的秩。LSA方法取矩陣F0的前k列，矩陣D0的前k行，矩陣S0的前k個(gè)奇異值所得矩陣相乘的積作為原始矩陣的近似X′，并得到Fk、Dk和Sk，從而將意圖特征和搜索日志映射到一個(gè)相同的k維語(yǔ)義空間。每個(gè)意圖特征由Fk的行向量表示，每個(gè)搜索日志的查詢意圖由Dk的列向量表示，又稱此列向量為搜索日志的意圖特征向量，這樣二者之間的關(guān)聯(lián)關(guān)系就可以使用常見(jiàn)的相似性度量方法進(jìn)行衡量，為用戶日志聚類提供了語(yǔ)義層面的依據(jù)。

2基于SOM的用戶搜索日志聚類

意圖特征向量可以邏輯表示搜索日志的查詢意圖，查詢意圖相同的搜索日志具有相似的意圖特征，為了提取出每個(gè)查詢?cè)~的不同查詢意圖，需要對(duì)查詢?cè)~相同的搜索日志按照意圖相似度的不同進(jìn)行聚類。

圖2　SOM網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.2　SOM network topology

SOM[10]是一種自組織特征映射聚類算法，基于神經(jīng)網(wǎng)絡(luò)的基本思想，模擬人腦自組織映射的工作原理，構(gòu)建包括輸入層和輸出層的SOM網(wǎng)絡(luò)。其拓?fù)浣Y(jié)構(gòu)如圖2所示，輸入層由n個(gè)數(shù)據(jù)節(jié)點(diǎn)構(gòu)成，輸出層則由m個(gè)聚類結(jié)果節(jié)點(diǎn)構(gòu)成，輸入節(jié)點(diǎn)和輸出節(jié)點(diǎn)之間相互連接，在訓(xùn)練過(guò)程中逐步迭代賦予各個(gè)連接以權(quán)重wij(i=1,2...n;j=1,2...,m)，使得對(duì)于相似性較高的輸入數(shù)據(jù)節(jié)點(diǎn)被自動(dòng)映射到相同的輸出聚類節(jié)點(diǎn)，形成聚類。本文將每個(gè)用戶搜索日志的意圖特征向量作為SOM網(wǎng)絡(luò)的輸入，通過(guò)SOM網(wǎng)絡(luò)自學(xué)習(xí)過(guò)程，將查詢?cè)~相同的用戶搜索日志，按照其查詢意圖的相似度進(jìn)行聚類。具體聚類過(guò)程如下:

1)隨機(jī)初始化網(wǎng)絡(luò)連接權(quán)重[(w11,...,wnm)]；

2)給出一個(gè)新的輸入向量[搜索日志的意圖特征向量]；

3)計(jì)算輸入向量與競(jìng)爭(zhēng)層的每一個(gè)神經(jīng)元的距離，當(dāng)前輸入向量i與第j個(gè)神經(jīng)元的距離D(j) 計(jì)算方式為

(2)

4)選擇競(jìng)爭(zhēng)層中與當(dāng)前輸入向量距離最近的神經(jīng)元作為獲勝神經(jīng)元；

5)賦予獲勝神經(jīng)元以及與其相鄰的神經(jīng)元以新的連接權(quán)重；

(3)

6)轉(zhuǎn)步驟2)，重復(fù)進(jìn)行以后各步直至所有搜索日志完成聚類。

3意圖提取

通過(guò)對(duì)具有相同查詢?cè)~的用戶搜索日志進(jìn)行聚類，搜索日志根據(jù)其意圖特征向量被劃分到不同的類中，每個(gè)類代表了查詢?cè)~的不同查詢意圖。意圖提取的主要思想是通過(guò)分析每個(gè)類實(shí)體對(duì)象的共同性以及不同類之間實(shí)體對(duì)象的差異性，提取出該類具有代表性的詞，組成意圖映射Ti，來(lái)描述該類的查詢意圖，如圖3所示。

圖3　意圖映射Fig.3　Intent mapping

根據(jù)上述思想，可把意圖提取過(guò)程分為類內(nèi)緊湊型提取、類間差異性提取及綜合提取三個(gè)部分，類內(nèi)緊湊型提取過(guò)程僅根據(jù)詞在一個(gè)類內(nèi)部的出現(xiàn)情況對(duì)其重要性進(jìn)行評(píng)價(jià)，類間差異性提取過(guò)程根據(jù)詞在不同類間出現(xiàn)的差異性對(duì)其重要性進(jìn)行評(píng)價(jià)，最后經(jīng)過(guò)綜合提取過(guò)程，把類內(nèi)緊湊型提取結(jié)果和類間差異性提取結(jié)果結(jié)合起來(lái)，對(duì)詞進(jìn)行綜合評(píng)價(jià)。抽取每個(gè)類代表性詞的依據(jù)是這個(gè)詞在該類的很多搜索日志中頻繁出現(xiàn)，而在其它類中很少出現(xiàn)。意圖提取算法描述如下：

輸入：所有意圖聚類的集合C，閾值λ；

輸出：意圖映射集T；

步驟：

1)Initialize: Foreach(TiinT)Ti=Φ；

2)Foreach(CiinC)

3) Foreach(tjinCi)

4) 類內(nèi)緊湊型提取：

5)類間差異性提?。?/p>

6)綜合提?。?/p>

if(Score(Ci,tj)>λ)addtjtoTi

7) returnT；

其中，λ為詞重要性評(píng)價(jià)閾值，freq(Ci,tj)表示詞tj在類Ci中出現(xiàn)的頻率，max(freq(Ci,t))表示Ci類中所有詞出現(xiàn)的最大頻率，ief(Ci,tj)表示詞tj在類Ci的實(shí)體中出現(xiàn)的概率，詞tj相對(duì)于類Ci的重要性與freq(Ci,tj)、ief(Ci,tj)成正比，而與該詞在所有類中出現(xiàn)的頻率成反比。

4用戶查詢意圖的識(shí)別

準(zhǔn)確識(shí)別用戶的查詢意圖并快速返回用戶實(shí)際需要的數(shù)據(jù)，對(duì)數(shù)據(jù)空間查詢服務(wù)質(zhì)量有重要影響。用戶查詢意圖識(shí)別大致分為兩個(gè)過(guò)程：

1)根據(jù)用戶歷史查詢?nèi)罩?，獲取能夠描述用戶查詢意圖傾向的數(shù)據(jù)特征的過(guò)程，即意圖傾向特征提取過(guò)程；

2)根據(jù)提取出來(lái)的意圖傾向特征，與用戶當(dāng)前查詢對(duì)應(yīng)的不同查詢意圖進(jìn)行匹配的過(guò)程，即意圖匹配過(guò)程。

4.1 意圖傾向特征提取過(guò)程

同一用戶不同情況下提出相同的查詢，查詢意圖卻不一定相同，用戶的興趣愛(ài)好、實(shí)時(shí)需求、數(shù)據(jù)流行度等多種因素都會(huì)影響到用戶的意圖傾向。而意圖傾向特征的提取就是要從用戶或者同類用戶的歷史日志中，找出與當(dāng)前查詢相同的所有搜索日志，從搜索日志中提取出能夠描述用戶意圖傾向的特征，并計(jì)算每個(gè)特征權(quán)重，組成意圖傾向特征向量，意圖傾向特征向量能夠反映出用戶訪問(wèn)數(shù)據(jù)的特點(diǎn)。下面將分別描述在用戶曾提出過(guò)相同查詢與用戶未提出過(guò)相同查詢兩種情況下意圖傾向特征的提取算法。

1)當(dāng)用戶曾提出過(guò)相同查詢時(shí)，從該用戶歷史查詢?nèi)罩局刑崛∫鈭D傾向特征的算法描述如下：

輸入：搜索日志集LOG，閾值w；

輸出：意圖傾向特征向量L；

步驟：

①Initialize:L=Φ；

血清CA19-9、CEA水平已被證實(shí)與胰腺癌的病情變化及對(duì)治療的反應(yīng)相關(guān)[4,12]，是目前胰腺癌診斷及預(yù)后判斷中應(yīng)用最為廣泛的2種血清腫瘤標(biāo)志物。近年研究發(fā)現(xiàn)血清CA125水平與胰腺癌的肝轉(zhuǎn)移及手術(shù)獲益相關(guān)[13-14]。血清CA242與CA724也是臨床中常用的與消化道腫瘤相關(guān)的腫瘤標(biāo)志物，但敏感度和特異度并不高。本研究結(jié)果顯示血清CA19-9和CEA水平升高是晚期胰腺癌患者預(yù)后不良的危險(xiǎn)因素，而血清CA242、CA125、CA724與患者預(yù)后的關(guān)系不明顯，再次證實(shí)血清CA19-9和CEA水平是預(yù)測(cè)胰腺癌患者的預(yù)后重要指標(biāo)。

②Foreach(tjinLOG)

⑦if(Weight(tj)>w) add to L；

⑧returnL；

其中，LOG表示用戶歷史查詢?nèi)罩局校c當(dāng)前查詢相同的所有搜索日志集合，freq(tj)表示詞tj在LOG中出現(xiàn)的頻率，max(freq(t))表示在LOG中所有詞出現(xiàn)的最大頻率，ief(tj)表示詞tj在LOG的實(shí)體中出現(xiàn)的概率，ILF(tj)表示詞tj在LOG的不同搜索日志中出現(xiàn)的概率，詞tj的權(quán)重與freq(tj)、ief(tj)、ILF(tj)均成正比，詞tj的權(quán)重越高，說(shuō)明它在LOG的實(shí)體、搜索日志中較為普遍存在，能夠描述用戶查詢所有數(shù)據(jù)的共同特點(diǎn)，可作為該用戶的意圖傾向特征。

2)當(dāng)用戶未提出過(guò)相同查詢時(shí)，從同類用戶歷史查詢?nèi)罩局刑崛∫鈭D傾向特征的算法描述如下：

輸出：意圖傾向特征向量L；

步驟：

①Initialize:L=Φ；

②Foreach(tjinLOG)

⑧if(Weight(tj)>w′)addtoL；

⑨returnL；

其中，U表示用戶所在的類中曾提出過(guò)當(dāng)前查詢的所有用戶，freq(tj)、ief(tj)、ILF(tj)的含義同從用戶歷史日志中提取意圖傾向特征的算法，與其不同的是，增加了IUF(tj)來(lái)表示詞tj在不同用戶的搜索日志中出現(xiàn)的概率，詞tj的權(quán)重越高，說(shuō)明它更能反映同類用戶查詢數(shù)據(jù)的共同特點(diǎn)，可作為該類用戶的意圖傾向特征。

4.2意圖匹配過(guò)程

通過(guò)搜索日志聚類與意圖提取，已經(jīng)得到了每個(gè)查詢對(duì)應(yīng)的幾種不同意圖，并采用意圖映射來(lái)描述每個(gè)查詢意圖，對(duì)于用戶當(dāng)前提出的查詢，意圖匹配的任務(wù)就是要根據(jù)用戶的意圖傾向特征及每個(gè)查詢意圖對(duì)應(yīng)的意圖映射，判斷用戶當(dāng)前查詢最可能屬于哪種意圖。意圖匹配算法描述如下：

輸入：意圖傾向特征向量L，意圖映射集T；

步驟：

1) Foreach(Ti∈T)

2)Foreach(tinTi)

5)k=argimax{sim(L,Ti)}；

其中，Sim(L,Ti)為用戶當(dāng)前查詢相對(duì)于每種意圖的傾向性度量，若描述某個(gè)查詢意圖的重要特征詞在用戶的歷史查詢?nèi)罩局谐霈F(xiàn)的概率越高，則用戶傾向于該查詢意圖的可能性就越大，最后，通過(guò)argimax{sim(L,Ti)}}返回傾向性最大的意圖類別，作為用戶當(dāng)前查詢的意圖。

5數(shù)據(jù)預(yù)取

在識(shí)別出用戶當(dāng)前查詢的意圖之后，該意圖所屬類中所有搜索日志都具有相同的查詢意圖，它們?cè)L問(wèn)的實(shí)體對(duì)象有許多共同的特點(diǎn)，對(duì)于其中比較流行訪問(wèn)的實(shí)體對(duì)象，很可能是當(dāng)前用戶查詢?cè)L問(wèn)對(duì)象。因此可根據(jù)該意圖所屬類中的用戶歷史查詢?nèi)罩?，提出一種數(shù)據(jù)預(yù)取策略。

6實(shí)驗(yàn)分析

6.1實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

硬件環(huán)境：Intel(R)Core(TM)i5，CPU3.20GHz，內(nèi)存4G，硬盤1TB。

數(shù)據(jù)集：目前針對(duì)數(shù)據(jù)空間領(lǐng)域并不存在公用的數(shù)據(jù)集，因此本實(shí)驗(yàn)從課題組為某單位開(kāi)發(fā)的數(shù)據(jù)空間信息管理系統(tǒng)β版本中，提取2014年1月至2014年11月500個(gè)用戶的2860910條查詢?nèi)罩咀鳛閷?shí)驗(yàn)數(shù)據(jù)集，其中，4/5作為訓(xùn)練集，其余作為測(cè)試集。用戶查詢?nèi)罩镜拿織l記錄包括有訪問(wèn)時(shí)間、訪問(wèn)用戶的ID、查詢搜索詞，訪問(wèn)實(shí)體ID、訪問(wèn)次序，數(shù)據(jù)路徑等信息。

6.2評(píng)價(jià)方法

為了對(duì)本文提出的預(yù)取方法進(jìn)行性能評(píng)價(jià)，本文引入如下性能指標(biāo)：

1)查詢響應(yīng)時(shí)間

執(zhí)行N個(gè)包含不同格式數(shù)據(jù)的查詢，在不同時(shí)刻執(zhí)行三次Q1、Q2、Q3，計(jì)算3個(gè)查詢的平均執(zhí)行時(shí)間作為查詢響應(yīng)時(shí)間:

(4)

其中，Responsetime表示查詢響應(yīng)時(shí)間，T1、T2、T3分別表示執(zhí)行三次查詢時(shí)間。

2)命中率

(5)

其中，HR表示命中率，|R|表示總共發(fā)出的訪問(wèn)請(qǐng)求數(shù)，R+表示所發(fā)出的訪問(wèn)請(qǐng)求中，數(shù)據(jù)已經(jīng)得到正確預(yù)取的請(qǐng)求數(shù)。

3)預(yù)取準(zhǔn)確率

(6)

其中，PR表示預(yù)取準(zhǔn)確率，P+表示預(yù)取出來(lái)的數(shù)據(jù)被訪問(wèn)的數(shù)目，P-表示預(yù)取出來(lái)的數(shù)據(jù)沒(méi)有被訪問(wèn)的數(shù)目。

4)網(wǎng)絡(luò)流量增加率

(7)

其中，ITR為網(wǎng)絡(luò)流量增加率，TP表示預(yù)取所有數(shù)據(jù)產(chǎn)生的網(wǎng)絡(luò)流量，TSP表示正確預(yù)取的數(shù)據(jù)產(chǎn)生的網(wǎng)絡(luò)流量，TP-TSP表示沒(méi)有正確預(yù)取的數(shù)據(jù)增加的網(wǎng)絡(luò)流量，TT是未使用預(yù)取時(shí)，讀取所有數(shù)據(jù)產(chǎn)生的網(wǎng)絡(luò)流量。

一般而言，預(yù)取準(zhǔn)確率越高，命中率越低，網(wǎng)絡(luò)流量增加率也較??；而查詢響應(yīng)時(shí)間則受命中率、網(wǎng)絡(luò)性能等多種因素影響。

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

6.3.1詞權(quán)重閾值對(duì)意圖識(shí)別效果的影響

由于詞的權(quán)重能夠反映同類用戶查詢數(shù)據(jù)的共同特點(diǎn)，不同的權(quán)重閾值選擇影響用戶的意圖傾向特征選擇的效果，為此，針對(duì)不同的閾值下，意圖識(shí)別效果進(jìn)行對(duì)比。圖4展示了針對(duì)用戶曾提出相同查詢情況，不同閾值w下意圖識(shí)別的準(zhǔn)確率對(duì)比，從圖中可知，閾值取0.14時(shí)，意圖識(shí)別準(zhǔn)確率最高。

圖4　不同閾值w下意圖識(shí)別準(zhǔn)確率對(duì)比Fig.4　Accuracy comparision of intent identification under different threshold w

圖5展示了針對(duì)用戶未曾提出相同查詢情況，不同閾值w′下意圖識(shí)別的準(zhǔn)確率對(duì)比，從圖中可知，閾值取0.025時(shí)，意圖識(shí)別準(zhǔn)確率最高。

圖5　不同閾值w′下意圖識(shí)別準(zhǔn)確率對(duì)比Fig.5　Accuracy comparision of intent identification under different threshold w′

6.3.2預(yù)取方法有效性驗(yàn)證

本文從兩個(gè)角度分別驗(yàn)證了預(yù)取方法的有效性：預(yù)取方法對(duì)查詢響應(yīng)時(shí)間的影響和預(yù)取的性能。

圖6展示了本文方法(QI)對(duì)查詢響應(yīng)時(shí)間的影響。與沒(méi)有采取預(yù)取的方法相比，明顯加快了查詢速度；另外，在不同流行度取值的情況下，其查詢響應(yīng)時(shí)間也不同，并且在閾值取0.65時(shí)其響應(yīng)時(shí)間最小，則預(yù)取方法此時(shí)效果最佳。

圖6　預(yù)取對(duì)查詢響應(yīng)時(shí)間的影響Fig.6　Response time comparision of theidentification under different popularity threshold μ′

圖7展示了本文方法(QI)性能情況。隨著流行度閾值取值越大，其預(yù)取準(zhǔn)確率越高，而命中率與網(wǎng)絡(luò)流量增加率則越低當(dāng)μ′取值小于等于0.25時(shí)，由于預(yù)取數(shù)據(jù)量過(guò)大，預(yù)取數(shù)據(jù)花費(fèi)了大量的時(shí)間，同時(shí)占據(jù)了大量的帶寬，雖然命中率比較高，但是預(yù)取的準(zhǔn)確率卻很低，所以并沒(méi)有提高查詢效率；當(dāng)μ′取值大于等于1.85時(shí)，由于預(yù)取的數(shù)據(jù)量很小，命中率較低，所以此時(shí)的查詢響應(yīng)效率與沒(méi)有預(yù)取時(shí)差不多。

圖7　預(yù)取效果評(píng)估Fig.7　Performance evaluation of our proposed method under different popularity threshold μ′

6.3.3不同方法對(duì)比

區(qū)別于已有的方法，本文方法(QI)采用基于查詢意圖的方法，從而更加個(gè)性化的預(yù)取，為此本節(jié)與已有方法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖8和圖9所示，其中實(shí)驗(yàn)時(shí)，流行度閾值選取0.65。

圖8　不同預(yù)取方法效果對(duì)比Fig.8　Effectiveness comparision of different prefetching proposals

圖9　不同預(yù)取方法性能對(duì)比Fig.9　Efficiency comparision of different prefetching proposals

從圖8和圖9中可知，本文提出的方法明顯優(yōu)于已有的方法，而且準(zhǔn)確率高達(dá)90%以上、時(shí)間僅為16.5s。這主要是由于預(yù)取結(jié)果中大部分與用戶意圖相吻合。

7結(jié)論

1)為了進(jìn)一步提高數(shù)據(jù)空間查詢效率，本文結(jié)合數(shù)據(jù)空間的特點(diǎn)及現(xiàn)有預(yù)取方法的優(yōu)缺點(diǎn)，在數(shù)據(jù)空間用戶提出查詢時(shí)，分析用戶查詢意圖，對(duì)用戶可能訪問(wèn)的數(shù)據(jù)進(jìn)行預(yù)測(cè)。

2)預(yù)取是在緩存技術(shù)的基礎(chǔ)上實(shí)現(xiàn)的，是緩存技術(shù)的擴(kuò)展，但本文沒(méi)有對(duì)緩存的替換策略、一致性更新策略等緩存管理機(jī)制進(jìn)行深入研究，未來(lái)可對(duì)具體緩存管理機(jī)制、用戶類型與流行度大小間關(guān)系、動(dòng)態(tài)預(yù)取等方面做深入研究。

參考文獻(xiàn)：

[1]FRANKLIN M, HALEVY A, MAIER D. From databases to dataspaces: a new abstraction for information management[J]. ACM SIGMOD record, 2005, 34(4): 27-33.

[2]TURAB MIRZA H, CHEN Ling, CHEN Gencai. Practicability of dataspace systems[J]. International journal of digital content technology and its applications, 2010, 4(3): 233-243.

[3]NANDINI N, YOGISH H K, RAJU G T. Pre-fetching techniques for effective web latency reduction - A survey[C]//Proceedings of IEEE AFRICON Conference. Pointe-Aux-Piments, 2013: 1-6.

[4]GAWADE S, GUPTA H. Review of algorithms for web pre-fetching and caching[J]. International journal of advanced research in computer and communication engineering, 2012, 1(2): 62-65.

[5]RAJU G T, SUDHAMANI M V. A novel approach for prefetching of web pages through clustering of web users to reduce the web latency[C]//Proceedings of International Conference On Advances In Computing. [S.l.], 2012: 983-989.

[6]邢永康, 馬少平. 多Markov鏈用戶瀏覽預(yù)測(cè)模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(11): 1510-1517.

XING Yongkang, MA Shaoping. Modeling user navigation sequences based on multi-Markov chains[J]. Chinese journal of computers, 2003, 26(11): 1510-1517.

[7]SHI Lei, GU Zhimin, PEI Yunxia, et al. A PPM prediction model based on web objects′ popularity[C]//Proceedings of the 2nd International Conference on Fuzzy Systems and Knowledge Discovery. Changsha, China: 2005: 110-119.

[8]XU Chengzhong, IBRAHIM T I. A keyword-based semantic prefetching approach in Internet news services[J]. IEEE transactions on knowledge and data engineering, 2004, 16(5): 601-611.

[9]KOU Gang, PENG Yi. An application of latent semantic analysis for text categorization[J]. International journal of computers, communications and control, 2015, 10(3): 357-369.

[10]ASTUDILLO C A, JOHN OOMMEN B. Topology-oriented self-organizing maps: a survey[J]. Pattern analysis and applications, 2014, 17(2): 223-248.

A dataspace prefetching method based on query intent

ZHU Guanwen，ZHOU Lianke，WANG Nianbin，LIU Dan

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Abstract：In order to prefetch the data that may be accessed by user before a query was posed, a novel prefetching method towards databaspace by exploiting query logs was proposed. Firstly, some intention features were extracted from the query logs, and the clustering technique was performed on the intention features. Secondly, the user query intention was identified. Finally, the query answers were prefetched according to the identified intention. The experimental results show that the proposed method can not only have a higher accuracy, but also improve the query efficiency, and it outperforms the existing methods.

Keywords：dataspace; prefetching; query intent; clustering; query logs; query answer; prefetch accuracy; query efficiency

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-7043(2016)02-0236-06

doi:10.11990/jheu.201411073

作者簡(jiǎn)介：祝官文(1986-), 男, 博士研究生;通信作者：周連科，E-mail：zhoulianke@hrbeu.edu.cn.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61272185); 黑龍江省自然科學(xué)基金資助項(xiàng)目(F201238, F020510);.中央高?；究蒲袠I(yè)務(wù)專項(xiàng)資金資助項(xiàng)目(HEUCFZ1219, HEUCF100608, HEUCF100613).

收稿日期：2014-11-24.網(wǎng)絡(luò)出版日期：2015-12-15.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151215.1141.030.html

周連科(1977-), 男, 講師;

王念濱(1967-), 男, 教授, 博士生導(dǎo)師.