P2P環(huán)境下的信息搜索與信息過濾研究

何 燕，何天云，唐曉玲

(四川外語(yǔ)學(xué)院圖書館，重慶 400031)

一、P2P網(wǎng)絡(luò)模型簡(jiǎn)介

P2P(Peer－to－Peer)稱為對(duì)等網(wǎng)絡(luò)或?qū)Φ冗B接，是一種流行的網(wǎng)絡(luò)模型。自出現(xiàn)之日起，P2P就已成為各個(gè)研究領(lǐng)域的熱點(diǎn)課題。近年來，P2P又運(yùn)用到數(shù)字圖書館領(lǐng)域，以分布和自組織的方式處理大量的數(shù)據(jù)。它采用的是社區(qū)組織形式，一個(gè)搜索引擎可以從大型用戶社區(qū)的智能輸入(書鑒、查詢?nèi)罩尽Ⅻc(diǎn)擊流等)中獲得益處［1］。這給數(shù)字圖書館的搜索能力提供了前所未有的優(yōu)勢(shì)，包括提高了可擴(kuò)展性、有效性、容錯(cuò)能力和動(dòng)態(tài)性等。但是，目前提出的結(jié)構(gòu)化P2P模型大多數(shù)是將用戶作為一個(gè)對(duì)等體，資源僅來自于數(shù)字圖書館及用戶本身，資源共享也只是用戶間的共享，而沒有將資源共享擴(kuò)大到數(shù)字圖書館之間。另外，目前的P2P技術(shù)局限于單個(gè)關(guān)鍵詞精確匹配的查詢，它不能滿足包含多個(gè)關(guān)鍵字的文本查詢［2］。并且，傳統(tǒng)的網(wǎng)頁(yè)搜索會(huì)得出海量的網(wǎng)頁(yè)數(shù)據(jù)，如果需要返回與關(guān)鍵字相匹配的、最相近的網(wǎng)頁(yè)列表，使用目前的P2P模型是完全行不通的［3］。

本文提出一種在數(shù)字圖書館的分布式P2P環(huán)境下而構(gòu)建的、新的信息搜索和信息過濾模型。模型將每個(gè)數(shù)字圖書館(Digital Library，簡(jiǎn)稱DL)看成是網(wǎng)絡(luò)中的一個(gè)對(duì)等體。模型底層的功能和數(shù)據(jù)均是分布在不同的對(duì)等體中，但對(duì)用戶提供統(tǒng)一的圖形用戶接口，以方便用戶使用。模型結(jié)構(gòu)如圖1所示。

圖1 P2P網(wǎng)絡(luò)模型

模型包含兩個(gè)部分:資源搜索模塊和信息過濾模塊。資源搜索模塊采用P2P技術(shù)分配和保存對(duì)等體統(tǒng)計(jì)數(shù)據(jù)，并完成一次查詢功能。根據(jù)相同的數(shù)據(jù)，信息過濾模塊針對(duì)一個(gè)連續(xù)查詢，選擇最可信的數(shù)字圖書館發(fā)布最合適的文檔，從而提供發(fā)布、定制服務(wù)［4］。

二、資源搜索模塊

P2P資源搜索模塊進(jìn)行資源搜索的步驟為:

(1)系統(tǒng)提供一個(gè)簡(jiǎn)單的搜索界面，允許用戶輸入查詢關(guān)鍵字。系統(tǒng)使用分布式哈希表(Distributed Hash Table，簡(jiǎn)稱DHT)啟動(dòng)全局查詢。分布式哈希表是將整個(gè)搜索空間對(duì)應(yīng)到一個(gè)散列空間，當(dāng)一個(gè)節(jié)點(diǎn)要搜索該資源時(shí)，對(duì)該資源的唯一標(biāo)志使用相同的散列函數(shù)進(jìn)行散列，得到散列值，再通過有效的局部路由，找到負(fù)責(zé)該資源的對(duì)等點(diǎn)［5］。它支持兩個(gè)哈希表函數(shù):插入關(guān)鍵字和對(duì)應(yīng)的值 insert(key，value)和檢索關(guān)鍵字 retrieve(key)。

(2)對(duì)于出現(xiàn)在查詢里的每個(gè)主題，系統(tǒng)檢索分布式目錄里所有合適的候選條目，也即通過輸入進(jìn)行查詢的路徑選擇。最終選擇一個(gè)可靠的數(shù)字圖書館子集，這些數(shù)字圖書館能夠針對(duì)指定查詢返回高質(zhì)量的結(jié)果。

(3)系統(tǒng)同樣使用DHT將用戶的查詢發(fā)送到已選擇的數(shù)字圖書館中，使用本地TOPX引擎評(píng)估搜索到的資源，對(duì)資源進(jìn)行降序排列，選擇排在前h位的資源(h由用戶自己確定)。

網(wǎng)絡(luò)爬行者用于模仿用戶的行為，瀏覽那些與特定用戶興趣主題相符合的網(wǎng)頁(yè)，并作出標(biāo)注［6］，從而搜集用戶的興趣。Topx是一個(gè)對(duì)XML和純文本數(shù)據(jù)進(jìn)行結(jié)果排序的搜索引擎［7］。其排序方法有兩種:一種是基于概率統(tǒng)計(jì)的評(píng)分模型，這種方法主要是根據(jù)用戶對(duì)資源的反饋來得出資源的評(píng)分，主要通過用戶對(duì)搜索到的資源的態(tài)度(點(diǎn)擊次數(shù)、瀏覽時(shí)間等)來決定分值的大小;另一種是根據(jù)資源的全文內(nèi)容，包括文中的短語(yǔ)、布爾表達(dá)式以及其他的限制條件進(jìn)行資源排序。

(4)綜合所有數(shù)字圖書館返回的資源，進(jìn)行去重、歸并，最后將結(jié)果顯示給用戶。

三、信息過濾模塊

相對(duì)于資源搜索模塊，信息過濾模塊的功能更加復(fù)雜。每個(gè)數(shù)字圖書館都需實(shí)現(xiàn)三類服務(wù):發(fā)布、定制和目錄服務(wù)。

發(fā)布服務(wù)的實(shí)現(xiàn)也需要一個(gè)網(wǎng)絡(luò)爬行者，其功能為發(fā)布信息資源。爬行者獲取用戶提供的信息，并將信息發(fā)布到網(wǎng)絡(luò)中。

定制服務(wù)首先由用戶將連續(xù)查詢發(fā)送到網(wǎng)絡(luò)中，系統(tǒng)選擇合適的對(duì)等體來標(biāo)引用戶的查詢。若選擇的對(duì)等體發(fā)布了與查詢匹配的資源，則向使用定制服務(wù)的用戶發(fā)出通知。與傳統(tǒng)的過濾模塊相比，此過濾模塊在進(jìn)行對(duì)等體選擇時(shí)，不僅使用了傳統(tǒng)的資源選擇算法，還引入了行為預(yù)測(cè)算法來描述對(duì)等體的行為趨勢(shì)。

最后，目錄服務(wù)負(fù)責(zé)將對(duì)等體加入P2P網(wǎng)絡(luò)，獲取對(duì)等體的信息檢索統(tǒng)計(jì)值。

四、P2P網(wǎng)絡(luò)模型的運(yùn)用

(一)資源的發(fā)布

一個(gè)對(duì)等體或數(shù)字圖書館希望將自己擁有的新文檔共享給網(wǎng)絡(luò)中的其他對(duì)等體，就需要發(fā)布資源。對(duì)等體在發(fā)布資源時(shí)，使用恰當(dāng)?shù)谋镜剡^濾算法將資源與本地查詢索引相匹配，若匹配成功，則觸發(fā)對(duì)定制該資源對(duì)等體的通知。執(zhí)行過程中，要求連續(xù)查詢的位置應(yīng)該固定，因?yàn)閷?duì)等體的查詢必須能被監(jiān)測(cè)到，這樣發(fā)布和通知過程均不需要額外的通信費(fèi)用。

(二)發(fā)布者的選擇

當(dāng)對(duì)等體p接收到一個(gè)來自用戶的連續(xù)查詢q時(shí)，p首先需要決定網(wǎng)絡(luò)中的哪些對(duì)等體為可以信任的候選對(duì)等體，并用這些對(duì)等體針對(duì)給定的連續(xù)查詢來發(fā)布相似的文檔。具體做法是，p針對(duì)q包含的每個(gè)主題向目錄服務(wù)發(fā)出請(qǐng)求，獲取每個(gè)對(duì)等體針對(duì)主題的統(tǒng)計(jì)值。綜合各主題的統(tǒng)計(jì)值得出各對(duì)等體的綜合評(píng)分，公式如下:

score(p，q)=(1 －a)*sel(p，q)+a*pred(p，q)其中，sel(p，q)表示資源選擇值，pred(p，q)表示對(duì)等體行為預(yù)測(cè)值，a為調(diào)整參數(shù)。通過上述公式的計(jì)算，將對(duì)等體按分值大小進(jìn)行降序排列，并將查詢q發(fā)送給排在最前面的K個(gè)對(duì)等體(K是用戶指定的參數(shù))。查詢q被存儲(chǔ)在這些對(duì)等體中，一旦這些對(duì)等體每次發(fā)布一個(gè)與查詢相匹配的資源，就向用戶發(fā)出通知。

每個(gè)查詢都包含一個(gè)生命周期值(TTL)，在指定的時(shí)間后應(yīng)該消失，保留查詢的對(duì)等體在查詢的生命周期過后應(yīng)將此查詢刪除。對(duì)等體p在發(fā)起下一次查詢過程時(shí)應(yīng)該進(jìn)行新的計(jì)算，選擇新的對(duì)等體。

(三)資源的選擇

函數(shù)sel(p，q)返回對(duì)等體p對(duì)查詢q的一個(gè)分值，計(jì)算這個(gè)分值采用信息檢索領(lǐng)域中標(biāo)準(zhǔn)的資源選擇算法。sel(p，q)表示對(duì)等體p在領(lǐng)域q內(nèi)的權(quán)威性，在我們的實(shí)驗(yàn)評(píng)估中，只考慮文檔頻率和主題頻率。文檔頻率(df)代表數(shù)字圖書館包含某個(gè)主題的文檔數(shù)量，主題頻率(tf)表示在數(shù)字圖書館的所有文檔中某主題出現(xiàn)的次數(shù)，而tfmax代表最大主題頻率，表示在數(shù)字圖書館的所有文檔中某主題出現(xiàn)的最大次數(shù)［9］。

(四)對(duì)等體的行為預(yù)測(cè)

對(duì)等體選擇過程的關(guān)鍵組成部分就是這里引入的預(yù)測(cè)機(jī)制。預(yù)測(cè)是資源選擇的補(bǔ)充，在過濾環(huán)境中是必要的。

假設(shè)數(shù)字圖書館dl1在足球方面相當(dāng)專業(yè)，是足球資料的權(quán)威，但它不再發(fā)布新的文檔。相反，數(shù)字圖書館dl2在足球方面不專業(yè)，但目前卻發(fā)布了關(guān)于足球的文檔。假設(shè)某個(gè)用戶定制關(guān)于將在南非舉行的2010年足球世界杯的文檔。只使用資源選擇算法的評(píng)分函數(shù)通常會(huì)選擇數(shù)字圖書館dl1作為資源的發(fā)布者，實(shí)際上這是錯(cuò)誤的。但要使數(shù)字圖書館dl2得到更高的質(zhì)量評(píng)分，并被選擇成為資源的發(fā)布者，它必須在足球方面專業(yè)化，這需要很長(zhǎng)的過程，而且對(duì)于不斷變化的動(dòng)態(tài)過濾環(huán)境來說是不合適的。因此，單獨(dú)的資源選擇算法是不充分的，特別是針對(duì)一些剛被發(fā)布的新主題，因?yàn)樾轮黝}的生命周期都較短，慢速的資源選擇算法是最壞的選擇。所以在動(dòng)態(tài)環(huán)境下，對(duì)等體預(yù)測(cè)算法比起慢速的資源選擇算法適應(yīng)能力更強(qiáng)。

在預(yù)測(cè)對(duì)等體行為的背后，主要將信息檢索統(tǒng)計(jì)值看作是時(shí)間連續(xù)數(shù)據(jù)，并使用統(tǒng)計(jì)分析工具模型化對(duì)等體的行為。時(shí)間連續(xù)分析假設(shè):發(fā)生在某時(shí)間段的數(shù)據(jù)有內(nèi)在的序列，并通過觀察來分析舊值，預(yù)測(cè)新值。例如，一個(gè)數(shù)字圖書館目前發(fā)布了大量的關(guān)于足球的文檔，將來同樣也會(huì)發(fā)布許多關(guān)于足球的文檔。

有兩種不同的技術(shù)預(yù)測(cè)未來值:平均值技術(shù)和指數(shù)滑動(dòng)技術(shù)。平均值技術(shù)是對(duì)過去的觀測(cè)值平均分布權(quán)重，不能很好地處理數(shù)據(jù)值的趨勢(shì)，這個(gè)缺陷比較致命。因此，我們使用第二種技術(shù)，指數(shù)滑動(dòng)技術(shù)。雙指數(shù)滑動(dòng)技術(shù)與單指數(shù)滑動(dòng)技術(shù)相比考慮到了數(shù)據(jù)趨勢(shì)，所以我們選擇雙指數(shù)滑動(dòng)技術(shù)模型化對(duì)等體的行為，并預(yù)測(cè)未來的發(fā)布行為。另外，針對(duì)更長(zhǎng)而持續(xù)的查詢，必須考慮活動(dòng)期的問題，應(yīng)考慮三指數(shù)滑動(dòng)技術(shù)。

(五)目錄維護(hù)

綜上所述，準(zhǔn)確的對(duì)等體統(tǒng)計(jì)值對(duì)于對(duì)等體質(zhì)量評(píng)分和對(duì)等體的選擇都是必需的。過濾模塊使用的是和資源搜索模塊相同的目錄，保存信息檢索統(tǒng)計(jì)值。此目錄是一個(gè)邏輯上統(tǒng)一而物理上分開的分布式目錄，采用分布式哈希表來管理壓縮形式的數(shù)字圖書館集成信息。在運(yùn)用中，我們使用Chord分布式哈希表劃分主題空間，這樣每個(gè)對(duì)等體負(fù)責(zé)目錄中的一個(gè)隨機(jī)主題子集的統(tǒng)計(jì)值。為了更新統(tǒng)計(jì)值，對(duì)等體與全局目錄保持一致。DHT決定一個(gè)對(duì)等體目前負(fù)責(zé)的主題，并且保存該主題的所有條目。

對(duì)等體實(shí)現(xiàn)的目錄服務(wù)不一定使用Chord，可使用其他DHT。因?yàn)椋@種結(jié)構(gòu)允許任何種類的P2P網(wǎng)絡(luò)(結(jié)構(gòu)化的和非結(jié)構(gòu)化的)使用，只要給出必須的信息，如每個(gè)對(duì)等體的信息檢索統(tǒng)計(jì)值等。

(六)實(shí)驗(yàn)結(jié)果

我們使用不同的發(fā)布場(chǎng)景，根據(jù)召回率(recall)測(cè)試系統(tǒng)性能，召回率用收到的通知數(shù)與發(fā)布的相關(guān)文檔數(shù)的比值表示。實(shí)驗(yàn)中，使用1000個(gè)發(fā)布者，分別用30個(gè)2、3和4主題連續(xù)查詢。每個(gè)對(duì)等體都是10類信息(類別包括音樂、體育等)中的很專業(yè)的一類。并在指定時(shí)間段內(nèi)發(fā)布30個(gè)文檔，在10次循環(huán)后，我們得出結(jié)果。然后改變存儲(chǔ)連續(xù)查詢的發(fā)布者百分比再進(jìn)行下一次實(shí)驗(yàn)。圖2為實(shí)驗(yàn)結(jié)果，橫坐標(biāo)p為發(fā)布者對(duì)等體占總發(fā)布者數(shù)量的百分比，縱坐標(biāo)表示平均召回率。實(shí)驗(yàn)結(jié)果顯示，使用行為預(yù)測(cè)與只使用資源選擇相比，召回率提高很明顯。將資源選擇與行為預(yù)測(cè)相結(jié)合，過濾模塊更加準(zhǔn)確地模型化了對(duì)等體的行為，可以預(yù)測(cè)對(duì)等體的行為趨勢(shì)。

五、信息搜索模塊與信息過濾模塊的比較

信息搜索模塊和信息過濾模塊分別處理系統(tǒng)的兩個(gè)不同問題，但兩種方法有相似之處。它們的重要屬性對(duì)比見表1。

圖2 資源選擇與行為預(yù)測(cè)召回率比較

表1 信息搜索模塊與信息過濾模塊的比較

六、結(jié)論

本文給出了一個(gè)系統(tǒng)模型，在數(shù)字圖書館的分布式P2P環(huán)境中，能夠有效地進(jìn)行信息搜索和信息過濾。P2P技術(shù)被用于構(gòu)建對(duì)等體統(tǒng)計(jì)值的分布式目錄。這個(gè)目錄用于對(duì)等體選擇，包括信息搜索和信息過濾兩種運(yùn)用場(chǎng)景。為了構(gòu)建這個(gè)目錄，系統(tǒng)可以使用不同的底層P2P系統(tǒng)，比如Chord和 Pastry。

信息過濾模塊與信息搜索模塊具有相似的構(gòu)成，都包括根據(jù)對(duì)等體統(tǒng)計(jì)值建立的分布式目錄。只是在信息過濾模塊中，對(duì)等體選擇最可信的數(shù)字圖書館去發(fā)布興趣文檔，從而滿足連續(xù)查詢。而對(duì)等體的選擇不僅使用了眾所周知的資源選擇算法，還使用了新的對(duì)等體行為預(yù)測(cè)算法。實(shí)驗(yàn)結(jié)果表明，采用這種方法進(jìn)行對(duì)等體選擇更加合理，提高了召回率。

［1］Matthias B，Sebastian M，Christian Z，et al.Bookmarkdriven query routing in Peer-to-Peer Web Search［C］//Proceedings of the SIGIR Workshop on Peer-to-Peer Information Retrieval，2004:1 －12.

［2］Huebsch R，Chun B，Joseph M，et al.The architecture of Pier:an internet-scale query processor［C］//Proceedings of the 2005 CIDR Conference，2005:28 －43.

［3］Matthias B，Sebastian M，Peter T，et al.Minerva:Collaborative P2P Search［C］//Proceedings of the 31st International Conference on Very Large Data Bases，2005:1263－1266.

［4］Tang C Q，Xu Z C.pFilter:Global Information Filtering and Dissemination using structured Overlay Networks［C］//The International Workshop on Future Trends of Distributed Computing Systems，2003:24 －30.

［5］Stoica I，Morris R，Karger D，et al.Chord:A scalable Peer-to-Peer Lookup Service for Internet Applications［C］//Proceedings of ACM SIGCOMM，2001:149－160.

［6］Bookmark-Induced Gathering of Information with Adaptive Classification into Personalized Ontologies［EB］.［2007－03－13］.http://www.mpi-inf.mpg.de/units/ag5/software/bingo/.

［7］Martin T，Ralf S，Gerhard W.An efficient and versatile query engine for topX search［C］//31st International Conference on Very Large Data Bases，2005:625 －636.

［9］Callan J.Distributed Information Retrieval［M］.Holland:Kluwer Academic Publishers，2000:127 －150.