PeertoPeer環(huán)境下基于內(nèi)容的智能搜索

《PeertoPeer環(huán)境下基于內(nèi)容的智能搜索》由會員分享，可在線閱讀，更多相關(guān)《PeertoPeer環(huán)境下基于內(nèi)容的智能搜索（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Peer-to-Peer環(huán)境下基于內(nèi)容的智能搜索 摘要 目前大多數(shù)P2P系統(tǒng)只支持基于文件標(biāo)識的搜索，大大限制了P2P的應(yīng)用范圍．純P2P網(wǎng)絡(luò)所采用的廣播式搜索盲目低效，浪費網(wǎng)絡(luò)帶寬．提出了P2P環(huán)境下基于內(nèi)容的智能搜索算法．利用向量空間模型進行基于相似度的查詢．節(jié)點對以往的查詢進行查詢聚類，對當(dāng)前的查詢，根據(jù)查詢類選擇最有可能包含查詢結(jié)果的節(jié)點發(fā)送查詢，提高了搜索的效率．隨著查詢的進行，查詢類可以自動調(diào)整，維護代價不大，具有自適應(yīng)的特點．實驗證明，基于內(nèi)容的智能搜索在保證查詢效果的前提下大大提高搜索的效率． 關(guān)鍵詞 P2P；相似度；聚類；智能搜索 中圖法分類號 TP311

2、 Intelligent Search based on content of documents in peer-to-peer network Abstract Most existing Peer-to-Peer (P2P) systems only support simple title-based search, which is limited in functionality. Broadcast search is widely used in pure P2P network, which is not efficient and costs a lot of

3、 bandwidth. An intelligent search algorithm based on content of document is proposed. Vector space model (VSM) is used to do similarity search. Each peer does query clustering with the past queries. For a new arriving query, the most possible peers that have the query answers are selected according

4、to the query cluster to send the query, which improves the search efficiency. With queries done, query clusters can be adjusted automatically with a little cost. It is proved by experiments that the intelligent search algorithm can greatly improve the search efficiency, and meanwhile guarantee the q

5、uery effectiveness. Key Words P2P; similarity; clustering; intelligent search  1 引言 目前大多數(shù)P2P系統(tǒng)只支持基于文件標(biāo)識的搜索，例如：Napster[1]和Gnutella[2]使用文件名進行搜索，DHT使用基于key（由Hash函數(shù)產(chǎn)生）的查找，代表系統(tǒng)為Chord[3]．這些系統(tǒng)都不支持基于內(nèi)容的搜索，大大限制了P2P的應(yīng)用范圍． 本文主要考慮如何在純的P2P環(huán)境下進行基于內(nèi)容的搜索．假設(shè)網(wǎng)絡(luò)中的每個節(jié)點都維護一個文檔集．給定一個查詢，可能是幾個關(guān)鍵字，一個短語，一個句子，或者一個段落，

6、搜索網(wǎng)絡(luò)中與查詢語義相近的文檔．我們利用向量空間模型VSM[4]（Vector Space Model）計算文檔和查詢的相似度，搜索網(wǎng)絡(luò)中的節(jié)點，返回與查詢相似的文檔． 純的P2P網(wǎng)絡(luò)（如Gnutella）中的搜索是一種廣播式的搜索，查詢被廣播發(fā)送給所有的鄰居節(jié)點，不管它們是否真正含有查詢結(jié)果．廣播式的搜索具有很大的盲目性，搜索效率低下，而且造成了網(wǎng)絡(luò)帶寬的極大浪費．我們提出了一種基于內(nèi)容的智能搜索算法，節(jié)點根據(jù)以往查詢提供的信息，進行Peer（節(jié)點）選擇，將查詢發(fā)送給那些最有可能包含查詢結(jié)果的鄰居節(jié)點，提高搜索的效率．我們采用的方法是根據(jù)查詢的內(nèi)容對查詢進行聚類．對當(dāng)前的查詢q，計算查詢類

7、與查詢q之間的相似度，選擇與q最為相似的查詢類，根據(jù)查詢類的文檔結(jié)果分布（不同鄰居節(jié)點返回的結(jié)果數(shù)），選擇返回結(jié)果最多的k個鄰居節(jié)點發(fā)送查詢．隨著查詢的進行，查詢類可以自動調(diào)整，維護代價不大，具有自適應(yīng)的特點．實驗證明，基于內(nèi)容的智能搜索在保證查詢效果的前提下大大提高了搜索的效率． 2 相關(guān)工作比較 廣播式的搜索是一種盲目的搜索，搜索效率低下．為了提高搜索的效率，研究者們提出了很多解決方法． 文[5]提出了幾種在P2P網(wǎng)絡(luò)中提高搜索效率的策略．逐步加深搜索（Iterative Deepening）在一定程度上提高了搜索的效率，但沒有解決消息廣播發(fā)送的問題．定向?qū)挾葍?yōu)先的搜索DBFS（Di

8、rected Breadth First Search）采用啟發(fā)式的搜索避免了查詢的廣播發(fā)送，但沒考慮查詢的語義．本地索引（Local Index）有助于提高搜索的效率，但索引維護的代價很大．Freenet[6]只支持key（由Hash函數(shù)產(chǎn)生）的查找，不支持基于內(nèi)容的查找，大大限制了它的使用范圍．路由索引（Routing Index）[7]與廣播式的搜索相比，提供了目標(biāo)節(jié)點的方向，循序漸進地達到之，不再是盲目的搜索，提高了搜索效率，但索引維護的代價很高，不適于經(jīng)常動態(tài)改變的P2P網(wǎng)絡(luò)．自適應(yīng)的概率搜索APS（Adaptive Probabilistic Search）[8]具有自學(xué)習(xí)的特點，

9、但它需要為每個對象建立索引，需要很大的存儲空間，而且它只支持對單個對象的查找，不支持對多個對象的查找． 基于內(nèi)容的智能搜索根據(jù)查詢聚類，選擇最有可能包含查詢結(jié)果的節(jié)點發(fā)送查詢，避免了消息的泛濫．根據(jù)查詢的內(nèi)容進行聚類，考慮了查詢的語義．隨著查詢的進行，查詢類可以動態(tài)更新，維護代價很小，具有自適應(yīng)的特點． 3 純P2P網(wǎng)絡(luò)中基于內(nèi)容的搜索 純P2P網(wǎng)絡(luò)（如Gnutella）中不存在中心服務(wù)器，各個節(jié)點的地位一樣，可以動態(tài)地加入和退出網(wǎng)絡(luò)，節(jié)點上數(shù)據(jù)的放置由用戶自己決定，網(wǎng)絡(luò)拓撲結(jié)構(gòu)是任意的． 假設(shè)網(wǎng)絡(luò)中的每個節(jié)點都維護一個文檔集，給定一個查詢（用一組關(guān)鍵字進行表示），搜索網(wǎng)絡(luò)中與查詢相似

10、的文檔．我們利用向量空間模型VSM（Vector Space Model）進行本地的文檔檢索． VSM是信息檢索中的廣泛使用的檢索模型，它用向量表示查詢和文檔：（w1, w2, w3…, wn），其中wi為第i個特征項的權(quán)重．一般選用詞作為特征項，詞的權(quán)重一般采用TF*IDF規(guī)則產(chǎn)生，TF（term frequency）表示詞頻，IDF（inverse document frequency）表示逆文檔頻率．TF*IDF規(guī)則綜合考慮了文檔中詞的頻率和文檔集中包含該詞的文檔數(shù)，保證詞頻高并且含該詞文檔數(shù)少的詞的權(quán)重越高．文檔中詞的權(quán)重通過如下TF*IDF公式計算： (1) 其

11、中，wi,j為詞 ti 在文檔dj中的權(quán)重，fi,j為詞ti在文檔dj中的詞頻，N為文檔的總數(shù)，ni為文檔集中出現(xiàn)ti的文檔數(shù)，分母為歸一化因子． 查詢向量的計算相對簡單，查詢中關(guān)鍵字的權(quán)重要么是1要么是0，如果該關(guān)鍵字在查詢中出現(xiàn)，則權(quán)重為1，否則為0．同樣，我們也對查詢向量進行歸一化處理． 文檔和查詢的相似度通過計算文檔向量和查詢向量的夾角余弦進行衡量，具體公式為： (2) 其中，,分別為文檔dj和查詢q的向量表 示，，，wi,j和wi,q分別對應(yīng)詞ti在文檔dj和查詢q中的權(quán)重．向量之間的夾角余弦通過計算向量的點積得到．由于文檔dj和查詢q的向量都經(jīng)過歸一化處理，因此相似度函數(shù)

12、又可以寫成：． 純P2P網(wǎng)絡(luò)中采用的是廣播式搜索．每個節(jié)點除了搜索它的本地索引，還將查詢廣播發(fā)送給它的所有鄰居節(jié)點進行搜索．搜索的范圍由查詢的跳數(shù)TTL（Time-to-live）給出，查詢每轉(zhuǎn)發(fā)一次，TTL減1，當(dāng)TTL等于0時，就停止傳播查詢．節(jié)點找到結(jié)果就把結(jié)果原路返回給查詢的發(fā)起節(jié)點．為防止回路的產(chǎn)生，每個查詢消息都有唯一編號．如果該查詢先前已經(jīng)收到，說明發(fā)生了回路，則不必再傳播它．Gnutella采用的查詢是基于文件名的，我們將查詢進行擴展，包含一組關(guān)鍵字．每個節(jié)點維護一個倒排索引，檢索與查詢相關(guān)的文檔，并根據(jù)VSM計算文檔與查詢的相似度．規(guī)定一個相似度的門檻值T，凡是與查詢的相似

13、度大于等于T的文檔均作為查詢結(jié)果返回．搜索TTL范圍內(nèi)的所有節(jié)點，得到與查詢相似的所有文檔． 4 基于內(nèi)容的智能搜索算法 廣播式的搜索盲目低效，浪費網(wǎng)絡(luò)帶寬．我們希望在搜索的過程中，節(jié)點可以根據(jù)以往查詢提供的信息，將查詢發(fā)送給那些最有可能包含查詢結(jié)果的鄰居節(jié)點，從而提高搜索的效率．我們采用的方法是對查詢進行聚類，然后根據(jù)查詢類對當(dāng)前的查詢進行Peer選擇．最后，根據(jù)Peer返回的結(jié)果對查詢類進行調(diào)整． 4.1 查詢聚類 每個節(jié)點保存以往的查詢結(jié)果，并對查詢進行聚類．我們根據(jù)查詢的內(nèi)容對查詢進行聚類．查詢之間的相似度通過計算查詢向量之間的夾角余弦得到，如式(2)．查詢聚類的算法我們采用K

14、-Means算法[9]．具體步驟如下： STEP 1：任意選擇kC個查詢，作為類中心的估計； STEP 2：對每一個查詢q，計算q與kC個類中心的距離（相似度，通過計算向量之間的夾角余弦得到），將q歸入到距離q最近的類別中； STEP 3：重新計算各類的中心，計算方法為所有查詢向量的算術(shù)平均； STEP 4：跳轉(zhuǎn)到STEP 2，直到各類中心穩(wěn)定． K-Means算法通過不斷的迭代，最終將查詢劃分為kC類，每類聚集在類中心周圍的一個小區(qū)域，而且類與類間是可以比較明顯地區(qū)分．K-Means算法的時間復(fù)雜度為，其中，nq表示總的查詢數(shù)，kC表示查詢類的個數(shù)，l表示算法收斂所需的迭代次數(shù)．一

15、般情況下，kC和l都事先固定，算法的時間復(fù)雜度變?yōu)橐粋€線性的復(fù)雜度．K-Means算法的空間復(fù)雜度為，只需要kC個查詢類和nq個查詢的存儲空間．我們可以限制nq的最大數(shù)目，并利用LRU（Least recently used，最近最少使用）策略進行淘汰，保證節(jié)點存儲常用的查詢． 4.2 利用查詢類進行Peer選擇 對同一類查詢，我們計算查詢的中心向量，用以表示查詢類，計算方法為所有查詢向量的算術(shù)平均．例如：q1, q2, q3為一類查詢，用C1表示該查詢類，，則C1的向量表示為． 為了進行Peer選擇，節(jié)點還需記錄查詢的結(jié)果分布，即不同鄰居節(jié)點返回的結(jié)果數(shù)．我們對同類查詢的文檔結(jié)果分布也

16、進行平均，用來表示查詢類的文檔結(jié)果分布．設(shè)查詢q的文檔結(jié)果分布為(Nq,1, Nq,2, …, Nq,n)，其中Nq,i為鄰居節(jié)點Pi返回的結(jié)果數(shù)，n為節(jié)點P的鄰居節(jié)點數(shù)．用|C|表示查詢類中查詢的個數(shù)，查詢類C的文檔結(jié)果分布為： , (3) 對當(dāng)前的查詢q’，計算每個查詢類與查詢q’的相似度，通過計算向量之間的夾角余弦得到，如式(2)．選擇與q’最為接近的查詢類C’，根據(jù)C’的文檔結(jié)果分布，將查詢發(fā)送給返回結(jié)果最多的k（k

17、3的文檔結(jié)果分布分別為(5, 10, 0)、(20, 0, 10)和(0, 5, 10)，表示從鄰居節(jié)點B、C、D返回的結(jié)果數(shù)．對查詢q1，，我們利用式(2）計算查詢q1與查詢類C1、C2、C3的相似度，，，，選擇與q1最相似的查詢類C1，根據(jù)C1的文檔結(jié)果分布，將查詢q1發(fā)送給節(jié)點B、C（假設(shè)k=2）；對查詢q2，，，，，不存在與q2相似的查詢類，將查詢q2廣播發(fā)送給節(jié)點B、C、D． 根據(jù)查詢類進行Peer選擇可能導(dǎo)致消息死鎖的形成，例如：節(jié)點A將查詢發(fā)送給鄰居節(jié)點B、C、D，它們都不包含查詢結(jié)果．節(jié)點B認為節(jié)點A、C、D是最好的鄰居節(jié)點（最有可能包含查詢結(jié)果），節(jié)點C認為節(jié)點A、B、D是

18、最好的鄰居節(jié)點，節(jié)點D認為節(jié)點A、B、C是最好的鄰居節(jié)點．這樣，消息形成死鎖，查詢不能發(fā)送到網(wǎng)絡(luò)中其他的節(jié)點上．為了解決這個問題，我們額外隨機選擇一小部分鄰居節(jié)點發(fā)送查詢，降低死鎖發(fā)生的概率． 下面，我們給出基于內(nèi)容的智能搜索算法IntelligentSearch．假設(shè)已經(jīng)通過K-Means算法對查詢進行聚類，生成kC個查詢類．IntelligentSearch根據(jù)已有的查詢類，進行Peer選擇，具體步驟如下： STEP 1：計算查詢q與每個查詢類的相似度．假如存在與查詢q相似的查詢類，選擇與查詢q最相似的查詢類C；否則，將查詢q廣播發(fā)送給節(jié)點P的所有鄰居節(jié)點； STEP 2：根據(jù)查詢類

19、C的文檔結(jié)果分布，選擇k個返回結(jié)果最多的節(jié)點發(fā)送查詢．為了避免消息死鎖的形成，額外隨機選擇幾個節(jié)點發(fā)送查詢； STEP 3：根據(jù)鄰居節(jié)點返回的查詢結(jié)果，記錄查詢q的文檔結(jié)果分布，保存查詢q； STEP 4：將查詢q歸入查詢類C，每隔一段時間利用K-Means算法重新調(diào)整查詢類． IntelligentSearch根據(jù)以往的查詢提供的信息，選擇最有可能包含查詢結(jié)果的節(jié)點發(fā)送查詢，避免了查詢的廣播發(fā)送，提高了搜索的效率． 4.3 查詢類的維護 對以往的查詢進行查詢聚類，隨著查詢的進行，查詢類可以自動調(diào)整，維護代價不大．IntelligentSearch的第4步，我們將查詢q歸入與q最相似

20、的查詢類C，重新計算查詢類的中心向量，得到新的查詢類C的向量表示．同時，根據(jù)查詢q的文檔結(jié)果分布，重新計算查詢類C的文檔結(jié)果分布．每隔一段時間，調(diào)用K-Means算法，調(diào)整查詢類． 基于內(nèi)容的智能搜索通過對查詢進行聚類，進行Peer選擇，提高了搜索的效率．同時，查詢聚類只需的時間（kC和l取常數(shù)），節(jié)點只需存儲的查詢以及查詢類，付出的額外代價很小．隨著查詢的進行，查詢類可以自動進行更新，維護代價也不大．實驗證明，基于內(nèi)容的智能搜索算法是有效的． 5 實驗 我們通過實驗驗證基于內(nèi)容的智能搜索算法的有效性，對算法的查詢效果和搜索效率進行實驗分析．查詢效果主要從用戶的角度考慮，反映系統(tǒng)的服務(wù)質(zhì)

21、量Qos（Quality of Service）；搜索效率主要從系統(tǒng)的角度進行考慮，力圖用最少的資源，獲得最多的輸出． 5.1 實驗設(shè)置 表4.1 實驗參數(shù) 表4.1 實驗參數(shù) 所有實驗都在一臺PC機上完成，PC機的配置為CPU P4 1.6GHz，內(nèi)存1GB，操作系統(tǒng)Windows XP．模擬程序由JAVA編寫，網(wǎng)絡(luò)拓撲結(jié)構(gòu)基于Power-law，由PLOD算法[10]產(chǎn)生．研究顯示Gnutella的網(wǎng)絡(luò)拓撲結(jié)構(gòu)接近Power-law[11]，Internet也符合Power-law規(guī)律，因此我們的模擬盡量接近現(xiàn)實中的P2P網(wǎng)絡(luò)．以下是實驗涉及的一些參數(shù)： 參數(shù)名稱 缺省

22、值 描述 Network Topology Power-law 網(wǎng)絡(luò)拓撲結(jié)構(gòu)，每個節(jié)點的平均出度為7 Network Size 1000 網(wǎng)絡(luò)中的節(jié)點數(shù) TTL 5 Time-to-live，查詢消息的跳數(shù) K 3 選擇K個節(jié)點發(fā)送查詢 ClusterNum 10 聚類的個數(shù) NewQueryNum 10 每個節(jié)點上新來10個查詢就重做一次K-Means，調(diào)整查詢聚類 注意：PLOD算法產(chǎn)生的網(wǎng)絡(luò)是一個無向圖，每個節(jié)點平均出度為7，相當(dāng)于無向圖中有3500條無向邊．實驗中，我們根據(jù)查詢類選取K個返回結(jié)果最多的節(jié)點發(fā)送查詢，并沒有象4.2節(jié)那樣，額外隨

23、機選擇幾個節(jié)點發(fā)送查詢以避免消息死鎖的形成． 測試文檔集我們采用SMART系統(tǒng)[12]中所使用的測試文檔集Cranfield，Cranfield包含1398個空氣動力學(xué)類文檔摘要和225個查詢．文檔集的分布采用80-20分布，即將80％的文檔分布在20%的節(jié)點上，余下的20%的文檔分布在80%的節(jié)點上，文檔不允許重復(fù)存放在多個節(jié)點上．80-20分布符合現(xiàn)實P2P系統(tǒng)的情況，網(wǎng)絡(luò)中只有少部分節(jié)點共享自己的文件，大部分節(jié)點只是搜索并下載文件． 5.2 查詢效果 判斷基于內(nèi)容的智能搜索算法(IntelligentSearch)的查詢效果，我們采用信息檢索中的查全率（Recall）進行衡量，Re

24、call的計算公式如下： (4) 其中，|Ra|為查詢結(jié)果中與查詢相關(guān)的文檔個數(shù)，|R|為文檔集中與查詢相關(guān)的文檔數(shù)． 我們將廣播式搜索的查詢效果作為測試的基準(zhǔn)，計算相對Recall作為查詢效果的衡量標(biāo)準(zhǔn)，計算公式如下： 相對Recall=Recall/廣播式搜索的Recall (5) 5.2.1 實驗1 IntelligentSearch的查詢效果 我們將Cranfiled的225個查詢分為兩部分，前100個查詢用來建立查詢聚類，后125個查詢用來測試查詢聚類對查詢效果的影響．從網(wǎng)絡(luò)中任選10個初始節(jié)點，先后執(zhí)行這兩部分查詢，計算

25、相對平均Recall,比較IntelligentSearch和RandomSelected（從所有鄰居節(jié)點中隨機選取K個節(jié)點發(fā)送查詢）的查詢效果，如圖1所示．可以看出，RandomSelected的相對平均Recall穩(wěn)定地維持在一個較低的水平，而IntelligentSearch的查詢效果大大好于RandomSelected的查詢效果，說明查詢聚類的方法是有效的．通過查詢聚類，我們選取了“較好”的K個鄰居，因此比隨機選取K個鄰居的效果更好．IntelligentSearch在訪問較少節(jié)點（K=3，只有網(wǎng)絡(luò)平均出度的一半不到）的情況下，依然能得到較好的結(jié)果（平均Recall是廣播式搜索的56.

26、9%，IntelligentSearch的查詢效果不如廣播式搜索，是由于它只選擇K個最有可能返回結(jié)果的節(jié)點發(fā)送查詢，搜索的節(jié)點沒有廣播式搜索多），因此是有效的．我們將在5.3節(jié)對搜索效率進一步用實驗說明． 圖1 IntelligentSearch和RandomSelected的相對平均Recall 圖2給出了IntelligentSearch和RandomSelected在查詢過程中的相對平均Recall，我們以10個查詢作為一個觀測點，計算10個查詢的相對平均Recall．QueryNo表示查詢的編號，QueryNo對應(yīng)的值表示QueryNo前后10個查詢的相對平均Recal

27、l． 可以看出，隨著查詢的進行，IntelligentSearch的查詢效果越來越好，這是由于隨著查詢數(shù)目的增加，節(jié)點上的查詢聚類越來越準(zhǔn)確，能為以后的查詢提供更好的參考．曲線在QueryNo=155時有抖動，是因為我們根據(jù)以往的查詢結(jié)果對當(dāng)前的查詢提供參考，隨著查詢的進行，聚類需要重新調(diào)整．RandomSelected由于沒有根據(jù)查詢類進行選擇，因此與查詢無關(guān)． 圖2 查詢過程中的相對平均Recall 5.2.2 實驗2 不同TTL情況下的查詢效果 IntelligentSearch的搜索范圍受到TTL的限制，不能訪問TTL之外的節(jié)點．增大TTL，可以提高IntelligentSe

28、arch的查詢效果，實驗結(jié)果如圖3所示． 圖3 IntelligentSearch在不同TTL情況下的相對平均Recall (K=3) 5.2.3 實驗3 增大K對查詢效果的影響 IntelligentSearch的搜索范圍不僅受到TTL的影響，還受到選擇節(jié)點個數(shù)（K）的影響．增大K可以提高查詢的效果，但也會影響查詢的效率，訪問更多的節(jié)點．增大K對搜索效率的影響我們將在5.3節(jié)中用實驗說明．圖4給出了IntelligentSearch和RandomSelected在TTL固定K增大的情況下的查詢效果．可以看出，隨著K的增大，IntelligentSearch和RandomSele

29、cted的查詢效果越來越接近，當(dāng)K接近網(wǎng)絡(luò)的平均出度時，這兩種算法的查詢效果接近廣播式搜索．因此，需要選擇一個合適的K，在兼顧搜索的效率的同時，提高查詢的效果． 圖4 增大K對查詢效果的影響(TTL=5) 5.3搜索效率 我們?nèi)〔樵冊L問的節(jié)點數(shù)VisitedNodeNum和傳遞的查詢消息數(shù)MsgNum作為衡量搜索效率的指標(biāo)．訪問的節(jié)點數(shù)越少，需要傳遞的查詢消息數(shù)就越少，搜索的效率就越高，需要付出的代價就越?。话銇碚f，VisitedNodeNum小于MsgNum，因為網(wǎng)絡(luò)中可能存在回路． 5.3.1 實驗4 IntelligentSearch的搜索效率 測試Intelligent

30、Search的搜索效率．同樣，從網(wǎng)絡(luò)中任選10個初始節(jié)點發(fā)送查詢，先執(zhí)行前100個查詢建立查詢聚類，再執(zhí)行后125個查詢測試查詢聚類的效果，計算平均訪問的節(jié)點數(shù)和發(fā)送的消息數(shù)，比較三種算法的搜索效率，如圖5所示． (a) 平均訪問的節(jié)點數(shù) (b) 平均發(fā)送的消息數(shù) 圖5三種搜索算法的搜索效率率 可以看出，IntelligentSearch和RandomSelected平均訪問的節(jié)點數(shù)還不到Broadcast的一半，需要發(fā)送的消息數(shù)更少，大約是Broadcast的四分之一． IntelligentSearch平均訪問的節(jié)點數(shù)和發(fā)送的消息數(shù)略多于RandomSelected，但

31、IntelligentSearch的查詢效果遠遠好于RandomSelected，見實驗1．因此IntelligentSearch是有效的，它提高了搜索效率，同時兼顧了查詢效果．比較圖5(a)和圖5(b)，可以發(fā)現(xiàn)，Broadcast發(fā)送的消息數(shù)（1296）遠遠大于訪問的節(jié)點數(shù)（719），說明查詢過程中發(fā)生了大量的回路．IntelligentSearch發(fā)送的消息數(shù)（330）略大于訪問的節(jié)點數(shù)（244），有效地避免了回路． 5.3.2 實驗5 增大K對搜索效率的影響 由實驗3，我們知道增大K可以提高查詢的效果，但同時也降低了搜索的效率，實驗結(jié)果如圖6所示． (b) 平均發(fā)送的消息數(shù) (

32、a) 平均訪問的節(jié)點數(shù) 圖6 增大K對搜索效率的影響(TTL=5) 可以看出，增大K，IntelligentSearch和RandomSelected平均訪問的節(jié)點數(shù)和消息數(shù)都隨之增加，越來越接近Broadcast．因此我們需要選擇一個合適的K，在提高搜索效率的同時，兼顧查詢的結(jié)果．  5 結(jié)論和未來工作 本文討論了P2P環(huán)境下基于內(nèi)容的搜索，提出了一種有效的基于內(nèi)容的智能搜索算法．對以往的查詢進行聚類，根據(jù)查詢類選擇最有可能包含查詢結(jié)果的節(jié)點發(fā)送查詢，提高了搜索的效率．查詢類可以隨著查詢的進行自動更新，維護代價小，具有自適應(yīng)的特點． 本文只考慮了基于相似度的查詢，利

33、用VSM模型檢索所有與查詢相關(guān)的文檔，并未對查詢結(jié)果進行排序，查詢結(jié)果中往往包含大量與查詢無關(guān)的文檔，同時也消耗了大量的網(wǎng)絡(luò)帶寬．我們希望對查詢結(jié)果進行排序，僅返回給用戶相似度最高的文檔，提高用戶的滿意度． 目前我們正在研究P2P環(huán)境下文檔集上的top-k查詢，已經(jīng)取得了部分研究成果，下一步將把top-k查詢擴展到數(shù)據(jù)管理的層次，進而擴大P2P搜索的范圍． 參 考 文 獻 1 Napster Home Page. 2 Gnutella Home Page. 3 I Stoica, R Morris et al. Chord: A scalable peer-to-peer lo

34、okup service for internet applications. ACM SIGCOMM Computer Communication Review, 2001, 31(4): 149~160 4 R Baeza-Yates, B Ribeiro-Neto. Modern information retrieval. Boston, MA: Addison Wesley, 1999. 27~30 5 B Yang, H Garcia-Molina. Efficient search in peer-to-peer networks. In: Proc of the 22nd

35、International Conference on Distributed Computing Systems. Vienna: IEEE Computer Society, 2002. 5~14 6 I Clarke, O Sandberg et al. Freenet: A distributed anonymous information storage and retrieval system. In: H Federrath ed. Proc of the Workshop on Design Issues in Anonymity and Unobservability. B

36、erkeley: Springer-Verlag, 2000. 46~66 7 A Crespo, H Garcia-Molina. Routing indices for Peer-to-Peer systems. In: Proc of the 22nd International Conference on Distributed Computing Systems. Vienna: IEEE Computer Society, 2002. 23~34 8 D Tsoumakos, N Roussopoulos. Adaptive probabilistic search (APS)

37、 for Peer-to-Peer networks. Technical report CS-TR-4451, University of Maryland, 2003 9 A Jain, M Murty. Data clustering: a review. ACM Computing Surveys, 1999, 31(3): 264~323 10 C Palmer, J Steffan. Generating network topologies that obey power law. In: Proc of GLOBECOM. San Francisco, CA: IEEE, 2000. 434~438 11 M Ripeanu. Peer-to-Peer architecture case study: Gnutella network. Technical Report, TR-2001-26, University of Chicago, 2001 12 C Buckley. Implementation of the SMART information retrieval system. Technical report, TR35-686, Cornell University, 1985