行車環境之高效能空間查詢

Abstract

在本計畫中，我們針對位置感知服務(Location Based Service)中最常用之NN/kNN查詢與Window/Range查詢服務提出一個整合方案，提昇行動位置相關服務系統的延展性與效能，並節省使用端行動裝置的能源消耗。在第一年中，我們首先研發整合NN/kNN查詢與Window/Range查詢服務的系統架構，藉以提升系統之延展性及其效能。同時，我們將為NN/kNN查詢之estimated valid region設計新的演算法。我們在第二年中，將為Window查詢引進合適索引結構；接著，我們將提出新的資料結構定義Window查詢之estimated valid region；最後，我們將研發快速Window查詢之estimated valid region計算演算法。在第三年中，我們將延伸Window查詢處理機制來支援Range查詢；此外也將設計有效演算法，讓NN/kNN查詢與Window/Range查詢的結果相互支援，進一步提昇系統效能。我們也將研發省電之行動裝置端(mobile client)與服務提供端(service provider)的溝通機制，來減少兩者之間的通訊量，進而降低行動裝置能源消耗。最後，我們將著手開發實驗平台並實作所開發之演算法，以便進行效能評估。

In this project, we aim to provide a scalable, energy-efficient system architecture supporting NN/kNN queries and window/range queries for location based services. In the first year, we will focus system architecture integration. Specifically, we integrate the components for window/range queries into our prior proxy-based system architecture for NN queries. In addition, we will design new algorithms for generating larger estimated valid regions of NN queries as well as kNN queries. In the second year, we will utilize Grid Index, propose a novel data structure of estimated valid regions, and develop an effective and efficient algorithm to create estimated valid regions for window queries. In the third year, we will extend the window query processing procedure to address range queries. Besides, we will propose several mechanisms to makes the results of NN/kNN queries support the resolving of window/range queries, and vice versa. With such mutual support, the overall system performance can be further enhanced. We expect that the accomplishment of the above will lead to an effective, efficient location-based queries processing system.