在P2P系統中建立捷徑以加速搜尋效率

Expediting Searching Processes via Long Paths in Peer-toPeer Systems

劉詩翾(Shih-Hsuan Liu)

指導教授 ： 陳宜欣

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2006年)

https://doi.org/10.6843/NTHU.2006.00573

摘要

P2P (Peer-to-Peer) 系統的研究者常依照使用者的興趣來建立捷徑以加速搜 尋速率。然而，這樣的捷徑建立方式會因為網路本身的成長讓捷徑以指數方式成長。為了探討這個議題，我們試著將social network的概念導入點對點系統中。因此，本研究旨在如何利用各項social network的概念來加快P2P network系統的搜尋過程以增進的搜尋效率。 本論文提出利用P2P系統中已連接節點的本地資訊，經由各節點獨特的social network，發掘有用的資源(潛在的朋友)，進而建立捷徑。本研究旨在擴大搜尋的範疇以迎合各種查詢的需要且維持一定的效率。 本實驗的分析是採用模擬的方式進行，目的是釐清social network特性如何幫助P2P系統中的搜尋。研究結果顯示我們的假設與實驗結果具有某些程度的一致性。總結而言，此研究希望能解釋如何利用social network特性來加速P2P系統的搜尋過程。

關鍵字

點對點網路 ； 社交網路 ； 六度分離

並列摘要

Researchers of Peer-to-peer networks (P2P) have often suggested that using interest-based shortcuts
to accelerate the searching process. However, the number of shortcuts in the most proposed
techniques exponentially increases with the size of the interest set. To address this issue, we attempt
to adapt social network concepts into P2P systems. Therefore, the objective of the paper
is to explore how to apply social network concepts and how those concepts are used to speed up
P2P searching process.
This paper describes an approach that exploits the local information of current connecting
peers in P2P systems to discover usable resources (latent friends) via individual’s unique social
networks, and then establishing long paths with them. This research involved a goal to broaden
the search scope to cater various kinds of query properties with limited maintenance cost but still
with certain efficiency.
The analysis of the experiments was conducted through simulation in order to indicate the relationship
between social network and P2P systems. The experimental results show some degree
of consistence with our hypotheses. To conclude, this study may be of importance in explaining
how the characteristics of social networks are used to beef up the query process in P2P system.

並列關鍵字

P2P ； Social Network ； Six Degrees of Separation

參考文獻

data access in p2p systems. IEEE Internet Computing, 6(1):58–67, 2002.

[2] Lada A. Adamic. The small world web. In Serge Abiteboul and Anne-Marie Vercoustre,

editors, ECDL, volume 1696 of Lecture Notes in Computer Science, pages 443–452.

social network of scientific collaborations. arXiv:cond-mat/0104162, 2001.

[5] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun.