歐幾理得空間下空間查詢之研究

Abstract

近年來，隨著具位置感知能力的行動裝置越來越普及，以及高速無線網路的覆蓋率越來越高，以位置為基礎之服務快速地受到使用者的歡迎。空間查詢是一種以位置為基礎之服務，其特點是根據查詢使用者當下位置為基礎，來擷取使用者感興趣之物件。空間查詢不但是非常有用的以位置為基礎之服務，同時空間查詢也廣泛應於於資料為基礎之行銷、決策支援、資源配置等等領域。由於空間查詢的高實用性，目前已有許多文獻探討空間查詢相關議題。這些文獻可約略區分為傳統空間查詢探索及新空間查詢介紹。有鑑於此兩範疇的重要性，本論文中我們各針對一範疇提出一個新的方法。

首先，我們針對傳統空間查詢探索於行動環境中，如何有效支援連續性查詢提出一新的以代理伺服器為基礎之方法。我們所提出之方法，其目標為有效率地提供有效的最近物件查詢與訊框查詢之預估有效區域給行動使用者，進而減少行動裝置所需傳送查詢之次數與後端伺服器負擔。對最近物件查詢部份，我們設計新的演算法使得代理伺服器可立即提供有效預估有效區域給行動使用者。我們所設計的演算法同時也可讓代理伺服器即使在快取空間有限時，都能夠建立有效的預估有效區域。另一方面，針對訊框查詢，我們提出使用新的向量表示法來代表預估有效區域（稱為預估訊框向量），來獲得較大的預估有效區域。 此外，我們也提出一演算法來迅速計算預估訊框向量。由於最近物件查詢與訊框查詢特性之不同，我們引進雙重索引結構，其中預估有效區域樹主要用於最近物件查詢處理，而網格則是應用於訊框查詢處理。為更進一步提昇整體效能，我們發展演算法使得雙重索引結構可相互支援。明確來說，網格索引將用以幫助回答最近物件查詢及延伸既有預估有效區域；最近物件查詢的答案則用以更新網格索引，以利預估訊框向量的計算。實驗結果顯示，與先前以代理伺服器為基礎之方法相比，我們所提出的方法可大幅提高使用者端快取成功比例、減少查詢解決時間、以及降低伺服器負擔。此外，從實驗結果也可以看出，雖然我們所提的方法只有部份的物件資訊，但其效能相當接近代表性以伺服器為基礎之方法。

此外，我們提出一新的空間查詢，稱作最近高密區查詢。一個高密區為一區域其長寬與使用者要求相同，並且至少包含使用者要求數目的物件。一最近高密區查詢會找出離查詢使用者當下位置最近的高密區。我們提出最近高密區查詢的動機在於，一個高密區可使得使用者在僅需移動有限距離下，即可體驗更多物件，並且更容易找到滿意的物件。為解決最近高密區查詢，我們介紹並發現一些特性來裨益發現高密區。根據這些特性，我們發展一基礎演算法來找出一最近高密區查詢之答案。雖然該基礎演算法可解決最近高密區查詢，我們又提出一高效率演算法來減少計算與I/O存取，進而加速最近高密區的尋找。新的高效率演算法主要包含高密區發現、搜尋區域縮減、與索引節點移除三項技術。高密區發現技術目標為避免計算不相關的物件，以及盡早結束高密區辨識，以求減少計算負擔。搜尋區域縮減技術利用已經發現之最佳高密區資訊來減少後續物件處理之計算；索引節點移除技術則是以已發現之最佳高密區資訊來嘗試免於存取某些索引節點。實驗結果顯示我們所提的高效率演算法可有效解決最近高密區查詢。

With the proliferation of location-aware mobile devices and the extensive coverage of wireless networks, location-based services (LBSs) have been rapidly gaining in popularity in recent years. Spatial queries, one of LBSs, are to retrieve the data objects of interest according to the locations of query users. In addition to being one useful LBS, spatial queries can be applied to a wide variety of applications such as profile-based marketing, decision support, and resource allocation. Due to a broad spectrum of applications of spatial queries, a significant number of research studies on spatial queries have been proposed and could be broadly classified into two categories, namely traditional spatial query exploration and new spatial query introduction. In this dissertation, we propose two works where one belongs to traditional spatial query exploration and the other new spatial query introduction.

In the first work, we propose a proxy-based approach to continuous spatial queries in mobile environments. The proposed approach aims to efficiently provide effective estimated valid regions (EVRs) of NN and window queries for mobile clients to reduce the numbers of submitted queries as well as the load on the query processing server. For NN queries, we devise novel algorithms to allow the proxy to immediately offer effective EVRs to mobile users. The algorithms also enable the proxy to build effective EVRs even when the proxy cache size is small. On the other hand, for window queries, we propose to represent the EVRs of window queries in the vector form, called estimated window vectors (EWVs), to achieve larger estimated valid regions. Besides, a companion algorithm is presented to create the EWVs in an efficient manner. Due to the distinct characteristics of NN and window queries, we employ different index structures, namely an EVR-tree for NN queries and a grid index for window queries. Moreover, to further increase the effectiveness and efficiency of the proposed approach, we develop algorithms to make the EVR-tree and the grid index mutually support each other. Specifically, the grid index is used to answer NN queries and extend existing EVRs. The answer objects of NN queries are exploited to update the grid index, benefiting the creation of more effective EWVs of window queries. The extensive experimental results demonstrate that the proposed approach significantly outperforms the existing proxy-based approaches in terms of client cache hit ratio, query answering time, and server load. Additionally, the results indicate that the performance of the proposed proxy-based approach is close to that of the representative server-based approach even though the proposed approach has only partial information of data objects.

In the second work, we propose and investigate a novel type of spatial queries,namely nearest dense window (NDW) queries. An NDW query $(q,l,w,k)$, a variant of NN queries, retrieves the nearest dense window of length $l$ and width $w$ containing at least $k$ data objects inside the window with respect to the query location $q$. The rationale of introducing the NDW query is that a region with a number of data objects is able to allow a query user to explore more objects and to be more likely to find satisfactory objects at a low moving cost. To answer NDW queries, we introduce and identify several properties to facilitate the identification of dense windows. Based on the properties, we develop a baseline algorithm to find the nearest dense window of an NDW query. Although the baseline algorithm can be used to answer NDW queries, we propose an NDW algorithm with less computation and I/O access to further increase the efficiency of NDW query search. The NDW algorithm mainly consists of three techniques, namely dense window discovery, search region reduction, and index node pruning. The dense window discovery technique attempts to avoid evaluating irreverent objects and to terminate the discovery as early as possible. The search region reduction and index node pruning techniques take advantage of the best distance found so far to reduce the search cost of objects and index nodes, respectively. The experimental results show that the proposed NDW algorithm is efficient in terms of I/O cost and query cost.