Unstructured P2P系統上之連續性Top-k查詢

Continuous Top-k Queries in Unstructured P2P Systems

高銘禧(Ming-Xi Gao)

指導教授 ： 陳宜欣

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

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

摘要

在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

並列關鍵字

p2p ； query

參考文獻

[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

[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.