臺灣博碩士論文加值系統

在P2P系統上對資料的搜索以及查詢的需求以及重要性越來越高，目前也有很多的研究正投入其中。
在各式各樣的P2P系統上的查詢中，對於在整個系統上找出與條件最有高度相關的前幾名的查詢，我們稱之為Top-k的查詢。
對於各樣在P2P系統上的應用軟體來說，
Top-k的查詢需求度越來越高。
但是在P2P上實做一個Top-k的查詢有很多的難題需要去克服。
P2P系統被人所知的特色包括了P2P的架構非常大，
每個peer在P2P上可以自由的加入或離去，
以及他的資料屬於動態的資料。
在這些特性下，傳統的資料庫系統所使用的查詢機制通常適用在靜態且穩定的檔案下，
假如應用在P2P的環境上，可能會導致產生很多不必要的傳輸的訊息，導致整體的傳輸以及計算上的花費過於龐大。
為了解決這些問題，我們在這篇論文中提出了一個有效率的解決方法來實行P2P系統上的Top-k查詢。
我們所使用的方法架構在一個Superpeer-Based的P2P系統環境下。
在Superpeer-Based的P2P系統,peer可以分為superpeer跟normal peer，由superpeer來觀測並收集normal peer上的資料。
把整體的機制以分散式的方法，分散到每個superpeer上以分擔這些工作。
在最後的實驗結果中，可以看出我們的方法在降低傳輸的花費上以及結果的精確度上都擁有不錯的成效。

The research of retrieving data 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. Designing top-k techniques in P2P systems is challenging. P2P systems are characterized
by large-scale, free peer behaviors, and dynamic data. Under the circumstances, the traditional query
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.
iv

Contents
Chinese Abstract ii
Abstract iii
1 Introduction 1
2 RelatedWorks 3
3 Methodology 5
3.1. Query Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Local Data Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3. Merging and Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Challenges in Peer-to-Peer systems 11
4.1. Storage Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2. Peers Come and Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Performance Evaluation 14
5.1. Experimental Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2. Experimental Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6 Conclusions 19
Bibliography 20

Bibliography
[1] Dataset: Can-o-sleep. http://kdl.cs.umass.edu/data/canosleep/canosleep-info.
html.
[2] Peersim: A peer-to-peer simulator. http://peersim.sourceforge.net/.
[3] B. Babcock and C. Olston. Distributed top-k monitoring. In Proceedings of the 2003 ACM SIGMOD international
conference on Management of data (SIGMOD’03), pages 28–39, 2003.
[4] W.-T. Balke, W. Nejdl, W. Siberski, and U. 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.
[5] A. Bulut and A. 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.
[6] R. Fagin. Combining fuzzy information: an overview. SIGMOD Rec., 31(2):109–118, 2002.
[7] R. M. Karp, S. Shenker, and C. H. Papadimitriou. A simple algorithm for finding frequent elements in streams
and bags. ACM Trans. Database Syst., pages 51–55, 2003.
[8] A. Manjhi, V. Shkapenyuk, K. Dhamdhere, and C. 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.
[9] G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proceedings of the 28th
International Conference on Very Large Data Bases, pages 346–357, 2002.