請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30285完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 周承復(Cheng-Fu Chou) | |
| dc.contributor.author | Yi-Ting Chang | en |
| dc.contributor.author | 張憶婷 | zh_TW |
| dc.date.accessioned | 2021-06-13T01:49:01Z | - |
| dc.date.available | 2010-03-19 | |
| dc.date.copyright | 2007-07-25 | |
| dc.date.issued | 2007 | |
| dc.date.submitted | 2007-07-09 | |
| dc.identifier.citation | [1] R. A. Hanneman and M. Riddle, Introduction to social network methods: Table
of contents. http://www.faculty.ucr.edu/ hanneman/nettext/, 2005. [2] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, Mak- ing gnutella-like p2p systems scalable,' in SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 407{418, 2003. [3] D. Stutzbach and R. Rejaie, Understanding churn in peer-to-peer networks,' in IMC '06: Proceedings of the 6th ACM SIGCOMM on Internet measurement, pp. 189{202, 2006. [4] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker, A scalable content-addressable network. ACM Press New York, NY, USA, 2001. [5] I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, et al., Chord: A Scalable Content-Addressable Network,' Proceedings of the ACM SIGCOMM 2001 Technical Conference, San Diego, CA, USA, August, vol. 1, 2001. [6] B. Zhao, J. Kubiatowicz, and A. Joseph, Tapestry: An Infrastructure for Fault- tolerant Wide-area Location and Routing,' Computer, vol. 74, 2001. [7] A. Rowstron and P. Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,' IFIP/ACM International Confer- ence on Distributed Systems Platforms (Middleware), vol. 11, pp. 329{350, 2001. [8] O. Gnawali, A keyword set search system for peer-to-peer networks,' jun 2002. Master's thesis, Massachusetts Institute of Technology. [9] P. Reynolds and A. Vahdat, E±cient peer-to-peer keyword searching,' in Pro- ceedings of International Middleware Conference, Jun 2003. [10] L. Liu and K.-W. Lee, Keyword fusion to support e±cient keyword-based search in peer-to-peer ‾le sharing,' in CCGRID '04: Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, pp. 269{ 276, 2004. [11] Y.-J. Joung, C.-T. Fang, and L.-W. Yang, Keyword search in dht-based peer- to-peer networks,' in ICDCS '05: Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), pp. 339{348, 2005. [12] Gnutella:http://www.gnutella.com/. [13] L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Bhuberman, Search in power-law networks,' Physical Review E, vol. 64 46135, 2001. [14] I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, Freenet: Adistributed anonymous information storage and retrieval system,' Lecture Notes in Com- puter Science, vol. 2009, pp. 46{66, 2001. [15] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, Search and replication in unstructured peer-to-peer networks,' in SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and mod- eling of computer systems, pp. 258{259, 2002. [16] C. Law and K.-Y. Siu, Distributed construction of random expander net- works.,' in INFOCOM 2003, 2003. [17] V. Vishnumurthy and P. Francis, On heterogeneous overlay construction and random node selection in unstructured p2p networks,' in INFOCOM, April 2006. [18] A. Rapoport, Mathematical models of social interaction,' Handbook of Math- ematical Psychology, vol. 2, pp. 493{579, 1963. [19] S. Wasserman and K. Faust, Social network analysis. Cambridge Univ. Press, 1995. [20] J. Scott, Social Network Analysis: A Handbook. Sage Publications, 2000. [21] S. Milgram, The small world problem,' Psychology Today, vol. 2, no. 1, pp. 60{67, 1967. [22] J. Travers and S. Milgram, An Experimental Study of the Small World Prob- lem,' Sociometry, vol. 32, no. 4, pp. 425{443, 1969. [23] H. Zhang, A. Goel, and R. Govindan, Using the small-world model to improve Freenet performance,' Computer Networks, vol. 46, no. 4, pp. 555{574, 2004. [24] D.Watts and S. Strogatz, Collective dynamics of'small-world'networks.,' Na- ture, vol. 393, no. 6684, pp. 409{10, 1998. [25] K. Lui and D. Yau, Small-World Overlay P2P Networks: Construction and Handling Dynamic Flash Crowd,' Computer Networks Journal, vol. 50, no. 15, pp. 2727{2746, 2006. [26] G. Feng, C. Li, Q. Gu, S. Lu, and D. Chen, SWS: Small World Based Search in Structured Peer-to-Peer Systems,' [27] P. Androutsos, D. Androutsos, and A. Venetsanopoulos, Small world dis- tributed access of multimedia data: an indexing system that mimics social acquaintance networks,' Signal Processing Magazine, IEEE , vol.23, no.2pp, pp. 142{ 153, Mar, 2006. [28] J. A. Pouwelse, P. Garbacki, J. W. A. Bakker, J. Yang, A. Iosup, D. Epema, M.Reinders, M. R. van Steen, and H. J. Sips, Tribler: A social-based based peer to peer system,' in 5th Int'l Workshop on Peer-to-Peer Systems (IPTPS), February 2006. [29] R. Baeza-Yates, B. Ribeiro-Neto, et al., Modern information retrieval. Addison- Wesley Harlow, England, 1999. [30] G. Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1989. [31] N. Linial and A. Wigderson, Expander graphs and their applications,' Lecture notes of a course: http://www. math. ias. edu/boaz/ExpanderCourse, vol. 4, 2003. [32] Napster: http://www.napster.com/. [33] V. Almeida, A. Bestavros, M. Crovella, and A. de Oliveira, Characterizing reference locality in the WWW,' Parallel and Distributed Information Systems, 1996., Fourth International Conference on, pp. 92{103, 1996. [34] K. Sripanidkulchai et al., The popularity of Gnutella queries and its implica- tions on scalability,' 2001. [35] K. Hui, J. Lui, and D. Yau, Small world overlay P2P networks,' Quality of Service, 2004. IWQOS 2004. Twelfth IEEE International Workshop on, pp. 201{210, 2004. [36] AudioScrobbler: http://www.audioscrobbler.net/. [37] Brite: http://www.cs.bu.edu/brite/. [38] A. Goel and R. Govindan, Using the small-world model to improve freenet performance,' Computer Networks Journal, vol. 46, no. 4, pp. 555{574, 2004. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30285 | - |
| dc.description.abstract | 隨著點對點網路系統的廣泛應用，多媒體物件的分享變得越來越有效率。點對點系統中的使用者會根據自己的喜好，搜尋及下載某特定類型的多媒體物件。然而，大多數的點對點系統只根據實體網路上的限制來建立疊代網路，並沒有考慮到系統中使用者對於物件的喜好。在這篇論文中，我們研究了一種以社群理論為基礎的疊代系統，能夠將點對點系統中有相同興趣的使用者聚集在一起，達成有效率的物件搜尋。為了要能夠建立以社群理論為基礎的疊代網路，我們提出了一個能夠計算使用者之間相似程度的量化方法，讓相似程度高的兩個使用者能夠在疊代網路上連結在一起。因此，使用者可以從與自己有相同興趣的鄰居中找到所感興趣的物件。此外，我們提出了一個讓使用者動態調整疊代網路上連結的分散式演算法，讓點對點網路系統能夠有效率地應付使用者的加入、離開，以及使用者興趣的變化。同時，我們提出了能夠處理多種物件類型的方法，及能夠增進物件搜尋效率的延伸方法，並且探討在限制TTL的情況下搜尋物件，應以多大的TTL值來做搜尋才能達到所希望的成功率。
我們利用名為Audioscrobbler網站上的使用者資料來做模擬實驗，以評估我們所提出的以社群理論為基礎的疊代網路系統。Audioscrobbler網站紀錄了使用者聆聽音樂的喜好，以及這些音樂的基本資料。實驗結果證實我們所提出的方法能夠讓使用者有效率地找尋到所想要的物件，即是能在造成系統較小的負擔下，達成很高的搜尋成功率。此外，我們也比較了傳統的非結構化點對點系統（以實體距離為基礎所建立的點對點疊代系統），實驗結果證實我們所提出的方法的確比傳統的點對點系統有較好的效能。 | zh_TW |
| dc.description.abstract | The widespread use of Peer-to-Peer (P2P) systems has made multimedia content sharing more efficient. Users in a P2P network can query and download objects based on their preference for specific types of multimedia content. However, most P2P systems only construct the overlay architecture according to physical network constraints and do not take user preferences into account. In this thesis, we investigate a social-based overlay that can cluster peers that have similar preferences. To construct a semantic social-based overlay, we model a quantifiable measure of similarity between peers so that those with a higher degree of similarity can be connected by shorter paths. Hence, peers can locate objects of interest from their overlay neighbors, i.e., peers who have common interests. In addition, we propose an overlay adaptation algorithm that allows the overlay to adapt to P2P churn and preference changes in a distributed manner. Meanwhile, we introduce methods to handle
multiple types of contents and extended methods to improve the performance of the content searching. We also analysis the number of TTL that is appropriate for the TTL-limited flooding. We use simulations and a real database called Audioscrobbler, which tracks users’ listening habits, to evaluate the proposed social-based overlay. The results show that social-based overlay adaptation enables users to locate content of interest with a higher success ratio and with less message overhead. Besides, we compare the performance between the proposed social-based p2p system with the Freenet-type p2p system. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T01:49:01Z (GMT). No. of bitstreams: 1 ntu-96-R94922039-1.pdf: 1145007 bytes, checksum: 516722620cb4e37b57844e719c8d7fa1 (MD5) Previous issue date: 2007 | en |
| dc.description.tableofcontents | Abstract (in Chinese) . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract (in English) . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem Formulation and Contribution . . . . . . . . . . . . . . . . . 2 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Decentralized P2P System . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 DHT-based P2P Systems . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Unstructured P2P Systems . . . . . . . . . . . . . . . . . . . . 7 2.2 Social-based P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Small World Theory . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Structured Social-based P2P Networks . . . . . . . . . . . . . 9 2.2.3 Unstructured Social-based P2P Networks . . . . . . . . . . . . 10 Chapter 3 Distributed Social-based Overlay Construction . . . . . 12 3.1 Overview of Social-based Overlay . . . . . . . . . . . . . . . . . . . . 12 3.2 Similar Peer Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.1 De‾nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.2 Similarity Computation . . . . . . . . . . . . . . . . . . . . . 14 3.2.3 Multiple Types of Contents . . . . . . . . . . . . . . . . . . . 15 3.3 Distributed Overlay Adaptation . . . . . . . . . . . . . . . . . . . . . 17 3.3.1 Distributed Buddy Selection . . . . . . . . . . . . . . . . . . . 18 3.3.2 Buddy List Update . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Keyword Search Using Social-based Graph . . . . . . . . . . . . . . . 20 3.4.1 Query TTL Analysis . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.2 Bu®er Replacement Schemes . . . . . . . . . . . . . . . . . . . 24 3.4.3 Enhanced Query Schemes . . . . . . . . . . . . . . . . . . . . 24 Chapter 4 Performance Evaluation and Discussion . . . . . . . . . 27 4.1 Experimental Environment . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Performance Comparison in Static Environments . . . . . . . . . . . 28 4.2.1 TTL-limited Flooding . . . . . . . . . . . . . . . . . . . . . . 30 4.2.2 Compare with Freenet-type P2P Networks . . . . . . . . . . . 33 4.3 Performance Comparison in Dynamic Environments . . . . . . . . . . 35 4.4 Multiple Types of Contents . . . . . . . . . . . . . . . . . . . . . . . 37 4.5 Enhanced Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.6 Query TTL Validation . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Chapter 5 Conclusions and Future Works . . . . . . . . . . . . . . 42 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 | |
| dc.language.iso | en | |
| dc.subject | 非結構化點對點網路 | zh_TW |
| dc.subject | 社群理論 | zh_TW |
| dc.subject | 關鍵字搜尋 | zh_TW |
| dc.subject | 多媒體存取系統 | zh_TW |
| dc.subject | Unstructured P2P Network | en |
| dc.subject | Social Theory | en |
| dc.subject | Keyword Search | en |
| dc.subject | Multimedia Access System | en |
| dc.title | 在非結構化點對點網路上以社群理論為基礎的有效率多媒體存取系統 | zh_TW |
| dc.title | Efficient Social-based Multimedia Access System in Unstructured P2P Networks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 95-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 吳曉光(Hsiao-kuang Wu),張英超(Ing-Chau Chang),楊峻權(Chun-Chuan Yang),林俊宏(Chun-Hung Lin),蔡子傑(Tzu-Chieh Tsai) | |
| dc.subject.keyword | 非結構化點對點網路,社群理論,關鍵字搜尋,多媒體存取系統, | zh_TW |
| dc.subject.keyword | Unstructured P2P Network,Social Theory,Keyword Search,Multimedia Access System, | en |
| dc.relation.page | 47 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2007-07-10 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-96-1.pdf 未授權公開取用 | 1.12 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。