跳到主要內容

臺灣博碩士論文加值系統

(100.26.196.222) 您好!臺灣時間:2024/02/26 16:09
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳俊柏
研究生(外文):Jyun-Bo Chen
論文名稱:P2P系統上之連續性Top-K查詢
論文名稱(外文):Continuous Top-K Query in Peer-to-Peer Systems
指導教授:陳宜欣陳宜欣引用關係
指導教授(外文):Yi-Shin Chen
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:27
中文關鍵詞:P2Ptop-kcontinuous
外文關鍵詞:P2Ptop-kcontinuous
相關次數:
  • 被引用被引用:0
  • 點閱點閱:123
  • 評分評分:
  • 下載下載:9
  • 收藏至我的研究室書目清單書目收藏:1
在許多領域的研究中,從 P2P 系統裡找資料已經變得愈來愈重要。在所有查詢相關的研究中, 能找出排名前K個物件的 Top-K 查詢在很多 P2P 網路應用是很急需的。然而,把在P2P 系統中導入 Top-K 技術會面臨一些困難: P2P 系統中有大量的電腦節點 (Peer)、每個 Peer 的行為不受拘束、 Peer 所含有的資料變動性很大。在這種情況之下,如果直接導入專為靜態環境和固定資料資料而設計的傳統 Top-K 技術將會產生過多、而且不必要的通訊量,進而影響整個 P2P 系統的效率。針對這些問題,我們在這篇論文中提出了一個有效的方法可以在 P2P 系統中執行連續性的 Top-K 查詢。這個架在 Superpeer 架構上的方法包含了1)可以掌握所有 Peer 最新動態的更新機制、和2)處理 Superpeer 之間資料傳遞的分散機制。根據我們的實驗結果,這個方法可以提供不錯的結果,同時也能減少了相當可觀的通訊量。
The research regarding locating specified resources in peer-to-peer (P2P) systems has become more and more important in many research communities nowadays. Among all query-related studies, the technique of top-k queries, which can locate the k objects with the highest overall rankings, is urgently demanded in many network applications. However, employing traditional top-k techniques in P2P systems faces some problems. P2P systems are characterized by large-scale, free peer behaviors, and dynamic data. Under the circumstances, the techniques designed for static environments and data would probably generate many unnecessary traffic messages and consume huge computation cost. To ease these problems, we propose an effective solution for continuous top-k query in P2P systems in this paper. The proposed technique, based on superpeer topology, consists of a reliable update mechanism between peers and a distributing mechanism between superpeers. As the experimental results show, the proposed technique can provide comparable results while reducing considerable communication cost.
Contents
1 Introduction 1
2 Related Work 5
3 Methodology 7
3.1 Naive Solutions for Continuous Query in P2P 7
3.2 Overview 8
3.3 P2P Topology 9
3.4 Constraint Design 10
3.5 Aggregate Mechanism
- From Client Peer to Superpeer 13
3.6 Aggregate Mechanism
- Among Superpeer Layer 14
4 Performance Evaluation 15
4.1 Measurement Metrics 15
4.2 Experimental Setting 16
4.3 Results and Discussion 18
5 Conclusions 23
Reference List 23

List Of Tables
3.1 Status of objects in P6 and P7 12
4.1 Parameters for CTK, NS1, and NS2 18

List Of Figures
1.1 Streaming data in P2P at time T1 (a) and T1 + 1 (b) 4
3.1 P2P system with superpeer topology 9
3.2 Routing paths of messages among the superpeer layer 10
4.1 Content of an update message 16
4.2 Lifetime distribution 17
4.3 Traffic 20
4.4 The original and the approximated data streams 21
4.5 Precision 22
[1] Bittorrent. http://bittorrent.com/.
[2] emule. http://www.emule-project.net/.
[3] Gnutella. http://www.gnutella.com/.
[4] Kazaa. http://www.kazaa.com/.
[5] The network simulator - ns-2. http://www.isi.edu/nsnam/ns/.
[6] Peersim: A peer-to-peer simulator. http://peersim.sourceforge.net/.
[7] Tools for peer-to-peer network simulation. http://tools.ietf.org/group/irtf/draft-irtf-p2prgcore-simulators-00.txt.
[8] Uci knowledge discovery in databases archive. http://kdd.ics.uci.edu/.
[9] Robert Alcock. Synthetic control chart time series, 1999. http://kdd.ics.uci.edu/databases/synthetic_control/synthetic_control.html.
[10] Brian Babcock and Chris Olston. Distributed top-k monitoring. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data (SIGMOD’03), pages 28–39, 2003.
[11] Wolf-Tilo Balke, Wolfgang Nejdl, Wolf Siberski, and Uwe Thaden. Progressive distributed top-k retrieval in peer-to-peer networks. In Proceedings of the 21st International Conference on Data Engineering (ICDE’05), pages 174–185, 2005.
[12] Ahmet Bulut and Ambuj K. Singh. Swat: Hierarchical stream summarization in large networks. In Proceedings of the 19th International Conference on Data Engineering (ICDE’03), pages 303–314, 2003.
[13] Clip2. The gnutella protocol specification v0.4, 2001.
[14] Ronald Fagin. Combining fuzzy information: an overview. SIGMOD Rec., 31(2):109–118, 2002.
[15] Donald Gross and Carl M. Harris. Fundamentals of Queueing Theory, 3rd ed. John Wiley & Sons, Inc., 1998.
[16] Fiorano Software Inc. Super-peer architectures for distributed computing., 2002. http://www.fiorano.com/whitepapers/superpeer.pdf.
[17] Richard M. Karp, Scott Shenker, and Christos H. Papadimitriou. A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst., pages 51–55, 2003.
[18] Jin Li, David Maier, Kristin Tufte, Vassilis Papadimos, and Peter A. Tucker. Semantics and evaluation techniques for window aggregates in data streams. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data (SIGMOD’05), pages 311–322, 2005.
[19] Jian Liang, Rakesh Kumar, and Keith W. Ross. Understanding kazaa, 2004.
[20] Amit Manjhi, Vladislav Shkapenyuk, Kedar Dhamdhere, and Christopher Olston. Finding (recently) frequent items in distributed data streams. In Proceedings of the 21st International Conference on Data Engineering (ICDE’05), pages 767–778, 2005.
[21] Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. In Proceedings of the 28th International Conference on Very Large Data Bases, pages 346–357, 2002.
[22] Alper Tugay Mizrak, Yuchung Cheng, Vineet Kumar, and Stefan Savage. Structured superpeers: Leveraging heterogeneity to provide constant-time lookup. In Proceedings of the Third IEEE Workshop on Internet Applications (WIAPP’03), pages 104–111, 2003.
[23] Alberto Montresor. A robust protocol for building superpeer overlay topologies. In Proceedings of the Fourth International Conference on Peer-to-Peer Computing (P2P’04), pages 202–209, 2004.
[24] Stefan Saroiu, P. Krishna Gummadi, and Steven D. Gribble. A measurement study of peer-to-peer file sharing systems. In Proceedings of Multimedia Computing and Networking,
pages 156–170, 2002.
[25] Subhabrata Sen and JiaWang. Analyzing peer-to-peer traffic across large networks. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment (IMW’02), pages 137–150, 2002.
[26] Mudhakar Srivatsa, Bugra Gedik, and Ling Liu. Scaling unstructured peer-to-peer networks with multi-tier capacity-aware overlay topologies. In Proceedings of the Parallel and Distributed Systems, Tenth International Conference on (ICPADS’04), pages 17–24, 2004.
[27] Chen Wang, Li Xiao, and Pei Zheng. Differentiated search in hierarchical peer-to-peer networks. In Proceedings of the 2005 International Conference on Parallel Processing (ICPP’05), pages 269–276, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top