自動調適快取法在P2P系統之連續性Top-K查詢研究

Adaptive Caching for Continuous Top-K Query in Peer-to-Peer Systems

孫偉程(Wei-Cheng Sun)

指導教授 ： 陳宜欣

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

摘要

Continuously monitoring the top-k objects distributed in networks has received considerable attention in recent years. In this paper, we focus on this problem in peer-to-peer (P2P) systems, which are characterized by large-scale, free peer behaviors and dynamic data. In order to get the top-k result in real time, many messages need to be transmitted, which creates tremendous traffic. Furthermore, when the system's peers leave, adjacent peers need to make a new connection and retransmit their data, which results in latency to obtain the result. Motivated by the work on sensor networks, we design a caching mechanism that reduces the traffic overhead and solves the latency problem effectively. The experimental results show that our proposed techniques can reduce traffic costs considerably and get an answer with high precision, even when many peers leave.

關鍵字

P2P ； 快取 ； Top-K

並列摘要

連續性的top-k監測散佈在網路上的資料在最近幾年備受關注。在本篇論文當中，我們特別針對P2P(Peer-to-Peer)網路上的問題做處理。P2P網路有幾個重要的特性，第一、網路規模大。第二、網路上的節點會隨時的加入以及離開。第三、每個節點上的資料是動態的。為了得到即時的top-k結果，許多的訊息必須被傳遞，這會造成很大的交通量。而且，當網路上的節點離開的時候，鄰接的節點必須重新建立連線後，才能繼續傳遞他們的資料。這會造成回傳結果的延遲。受到感測網路上研究的啟發，我們設計一個快取的方法，可以有效解決交通量以及回傳結果延遲的問題。實驗結果顯示，我們提出的方法，可以減少相當多的交通量。並且當許多的節點離開的時候，我們仍然可以維持相當高的準確率。

並列關鍵字

P2P ； Cache ； Top-K

參考文獻

[2] Peersim: A peer-to-peer simulator.

[3] R. Akbarinia, E. Pacitti, and P. Valduriez. Reducing network traffic in unstructured p2p systems

using top-k queries. Distrib. Parallel Databases, 19(2-3):67–86, 2006.

[4] R. Akbarinia, E. Pacitti, and P. Valduriez. Best position algorithms for top-k queries. In

495–506. VLDB Endowment, 2007.