行動環境上之高效能與省電之KNN查詢處理系統之研究

Abstract

在眾多無線網路服務媒體所提供的服務查詢中，以 Nearest Neighbor (NN)查詢與 k-Nearest Neighbor (k-NN)查詢最為常見。舉例來說：人們在下了火車離開火車站後， 通常想找離火車站最近(NN)的飯店休息，因此他會要求服務媒體提供離火車站最近飯 店的位址資訊；在市區中的汽車駕駛想要從他現在的位址連接到高速公路上，因此他 會要求服務媒體提供離他目前位址最靠近的k 個(k-NN)交流道位址資訊。研究文獻結 果指出，在行動資訊系統與行動設備間架設支援k-NN 查詢的proxy 能在少量增加建置 成本的情形下，有效地增快查詢的反應時間與降低行動資訊系統的總工作量。因此在 本計畫中，我們想要針對NN 與k-NN 查詢服務提出一個方案，提昇行動資訊系統的延 展性與效能，並節省使用端行動設備的能源消耗。我們將研發適用於行動計算環境下 之支援k-NN 查詢的系統架構，其主要議題如下：在第一年中，我們首先將研發提供整 合NN 查詢服務的系統架構，用以提升行動資訊系統的延展性與系統效能；接著我們 將研發快速的estimated valid region 成長方法；最後我們將研發合適之快取管理演算 法。在第二年中，我們將著重於k-NN 查詢。我們首先將修改之前設計之系統架構以支 援k-NN 查詢。我們也將著手研發省電之行動設備端(mobile client)與服務提供端(service provider)的溝通機制，由於行動設備大部分消耗電源在於與伺服器通訊，如果能有效的 減少行動設備與伺服器的通訊量，將有效的減少行動設備的能源消耗。因此我們將研 發適合行動資訊系統與行動設備的溝通機制，並將其與proxy 整合，減少proxy 與行動 設備間資料的傳輸量，並藉以減少行動設備的能源消耗。最後，我們將著手開發實驗 平台並實作所開發之演算法，以便進行效能評估。

In most mobile services, location-dependent queries are deemed killer applications of next generation mobile services. According to spatial constraints of queries, location-dependent queries can be divided into several categories including proximity query and k nearest neighbor query (referred to as k-NN query). A proximity query to find all objects within a certain range. An example proximity query is 「Find all taxis with distance less than 300 meters to me.」 Proximity queries are also known as range queries or window queries. A k-NN query is to find k nearest objects to a specific location (referred to the query location of the k-NN query). For example, a user may issue a k-NN query like 「Find the five nearest hotels」. A nearest neighbor query (referred to as NN query) which finds the nearest object to a specific location is a special case of k-NN queries with k = 1. For example, passengers will query the nearest hotels for taking a rest. In addition, drivers will query the k nearest gas stations for refueling. Research work shows that deploying proxies supporting NN and k-NN queries is able to greatly reduce system response time and system workload at the cost of slightly deployment cost. In this project, we aim to provide a scalable and energy-efficient system architecture supporting NN and k-NN queries. In the first year, we will focus on NN queries. Specifically, we will first develop a 3-tier system architecture for NN services. We will develop an effective algorithm to speedup the growth of estimated valid region. In addition, cache management algorithms will also be developed. In the second year, we will concentrate on the issues of k-NN queries. We will first extend the proposed architecture for supporting k-NN queries. In addition, the devised cache management algorithm will also be extended for k-NN queries. We will also address some problems dedicated for k-NN queries. Then, we will develop an experimental platform. Finally, we will implement the devised algorithms on the experimental platform to perform performance evaluation.