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

何 燕，何天云，唐曉玲

(四川外語學院圖書館，重慶 400031)

一、P2P網(wǎng)絡模型簡介

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

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

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

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

二、資源搜索模塊

P2P資源搜索模塊進行資源搜索的步驟為:

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

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

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

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

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

三、信息過濾模塊

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

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

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

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

四、P2P網(wǎng)絡模型的運用

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

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

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

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

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

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

(三)資源的選擇

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

(四)對等體的行為預測

對等體選擇過程的關鍵組成部分就是這里引入的預測機制。預測是資源選擇的補充，在過濾環(huán)境中是必要的。

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

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

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

(五)目錄維護

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

對等體實現(xiàn)的目錄服務不一定使用Chord，可使用其他DHT。因為，這種結構允許任何種類的P2P網(wǎng)絡(結構化的和非結構化的)使用，只要給出必須的信息，如每個對等體的信息檢索統(tǒng)計值等。

(六)實驗結果

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

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

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

圖2 資源選擇與行為預測召回率比較

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

六、結論

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

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

［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.