非合作性環(huán)境下的P2P搜索技術(shù)研究.pdf

1、為了解決傳統(tǒng)集中式搜索引擎所面臨的性能瓶頸，研究人員提出將搜索引擎構(gòu)建于P2P網(wǎng)絡(luò)之上，通過P2P網(wǎng)絡(luò)將分散的眾多節(jié)點(diǎn)聯(lián)系起來，整合它們的運(yùn)算能力和存儲(chǔ)資源，從而以較低的硬件代價(jià)形成巨大的服務(wù)性能。P2P搜索引擎的特點(diǎn)是每個(gè)節(jié)點(diǎn)都是一個(gè)獨(dú)立文檔數(shù)據(jù)庫(kù)，各節(jié)點(diǎn)處于對(duì)等地位，不存在中央節(jié)點(diǎn)，相互協(xié)作地響應(yīng)查詢請(qǐng)求。
　　 目前P2P搜索引擎的實(shí)現(xiàn)依賴一個(gè)假設(shè)：所有節(jié)點(diǎn)是合作性的，即所有節(jié)點(diǎn)能夠按照統(tǒng)一協(xié)議返回資源描述、參與維護(hù)索引、

2、轉(zhuǎn)發(fā)或執(zhí)行查詢等等。通常情況下，這種合作性機(jī)制是由每個(gè)節(jié)點(diǎn)安裝一個(gè)客戶端工具來實(shí)現(xiàn)的。然而，Web中有許多站點(diǎn)包含大量高質(zhì)量的文檔，且能夠提供站內(nèi)檢索服務(wù)，例如新聞網(wǎng)站，論壇，電子圖書館。這些資源節(jié)點(diǎn)屬于不同的商業(yè)公司或機(jī)構(gòu)，難以要求這類節(jié)點(diǎn)能夠合作地遵照統(tǒng)一協(xié)議參與系統(tǒng)的運(yùn)行。在文獻(xiàn)中，這類節(jié)點(diǎn)常被稱為非合作性節(jié)點(diǎn)，包含非合作性節(jié)點(diǎn)的運(yùn)行環(huán)境被稱為非合作性環(huán)境。由于Web中非合作節(jié)點(diǎn)數(shù)量巨大，整合這類資源將極大地提高搜索引擎的查詢質(zhì)量

3、和效果。
　　 本論文提出一個(gè)非合作性環(huán)境下的P2P搜索引擎框架，并基于這個(gè)框架，深入研究了P2P搜索引擎的關(guān)鍵問題，包括資源描述獲取方法，資源選擇算法，結(jié)果合并算法，索引目錄維護(hù)機(jī)制等，取得了若干研究成果。
　　 具體來說，本文的研究成果包括：
　　 (1)本文提出一種非合作性環(huán)境下的P2P搜索引擎架構(gòu)，稱為PISA(P2P InformationSearch with unccoperAtive Peers)

4、，實(shí)現(xiàn)融合非合作性節(jié)點(diǎn)。本文給出PISA的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、索引目錄的數(shù)據(jù)結(jié)構(gòu)及構(gòu)建過程、PISA的查詢過程。
　　 (2)本文提出一種非合作性環(huán)境下的啟發(fā)式查詢采樣方法HQBS(Heuristic Query-based Sampling)，從非合作性節(jié)點(diǎn)中獲取資源描述信息。傳統(tǒng)的方法是對(duì)非合作性節(jié)點(diǎn)發(fā)起一系列查詢，并下載若干結(jié)果文檔。當(dāng)采樣文檔達(dá)到一定數(shù)量時(shí)，停止采樣文檔。這種方法在P2P環(huán)境中容易造成對(duì)大節(jié)點(diǎn)采樣不足和對(duì)小節(jié)點(diǎn)

5、過度采樣。針對(duì)這些問題，HQBS方法采用啟發(fā)式判定采樣終止的條件，使得采樣
　　 文檔的數(shù)量能夠依節(jié)點(diǎn)大小而動(dòng)態(tài)調(diào)整，盡可能對(duì)每個(gè)節(jié)點(diǎn)都獲取高質(zhì)量的資源描述信息，且不浪費(fèi)采樣資源。
　　 (3)本文提出一種非合作性環(huán)境下的兼顧重疊和相關(guān)度的資源選擇算法OPS(Overlap-aware Peer Selection)。與傳統(tǒng)的資源選擇算法忽略資源間重疊不同，OPS用于在非合作性環(huán)境下，通過對(duì)查詢結(jié)果提取覆蓋統(tǒng)計(jì)信息，近似

6、地估算出節(jié)點(diǎn)資源間的重疊度，實(shí)現(xiàn)兼顧重疊和相關(guān)度的資源選擇算法，提高查詢的效率。隨著查詢的進(jìn)行，OPS提取的覆蓋統(tǒng)計(jì)信息越來越全面，OPS能夠有效地提高新穎結(jié)果的總量。
　　 (4)本文提出非合作環(huán)境下的兩個(gè)結(jié)果合并算法RISE/RISE+(Result mergIng inScore-absent Environments)，將非合作性節(jié)點(diǎn)返回的結(jié)果列表合并成單個(gè)有序的結(jié)果列表。傳統(tǒng)的方法依賴各資源節(jié)點(diǎn)提供的本地相關(guān)度分值(l

7、ocal relevancescore)，通過一系列的映射規(guī)范化等操作，計(jì)算得到全局相關(guān)度分?jǐn)?shù)。然而，在非合作性環(huán)境下，節(jié)點(diǎn)在返回的結(jié)果時(shí)，可能并不附帶本地相關(guān)度分值。本文提出兩種結(jié)果合并算法RISE/RISE+，能夠在非合作性節(jié)點(diǎn)不返回相關(guān)度分值的情況下，實(shí)現(xiàn)高效的結(jié)果合并。實(shí)驗(yàn)結(jié)果表明，這兩種算法的結(jié)果合并準(zhǔn)確性略高于傳統(tǒng)方法。
　　 (5)本文提出一種非合作性環(huán)境下的索引目錄更新機(jī)制CSU，使得索引目錄在節(jié)點(diǎn)顛簸(chur

8、n)和內(nèi)容演化時(shí)保持更新。傳張的索引目錄更新機(jī)制是一種基于生命周期(Time-To-Live，TTL)定時(shí)更新。各節(jié)點(diǎn)在每隔TTL時(shí)間更新索引目錄一次。這種方法在各節(jié)點(diǎn)顛簸，內(nèi)容演化速率相差很大時(shí)，系統(tǒng)難以選擇一個(gè)合適的TTL值。如果TTL過大，造成索引目錄更新不及時(shí)，影響資源選擇的準(zhǔn)確度；反之，會(huì)造成索引目錄維護(hù)開銷過大，影響系統(tǒng)的性能。針對(duì)這些問題，本文提出一種更為節(jié)約高效的非合作性環(huán)境下的索引目錄更新機(jī)制CSU。CSU基于受控更新