空間資料於分散式資料庫上的查詢與處理

Abstract

近年來，隨著行動裝置的普及與無線網路的高覆蓋率，地理位置服務 (location-based service, LBS) 已成為相當受歡迎的應用。在地理位置服務中，有一類服務稱為空間查詢（spatial query）可讓使 用者搜尋位於其位置附近的感興趣物件。由於空間查詢的實用性與便利性，空間查詢是相當熱門的研究 課題。然而，隨著空間資料的迅速增加，如何有效儲存及索引龐大的空間資料，以利於快速解決空間查 詢，乃是一個重要的問題。在本論文中，我們將利用分散式資料庫系統HBase來儲存龐大的空間資料， 並針對最常見的kNN (k nearest neighbor)查詢與window查詢，設計適合HBase之索引結構與查詢演算 法，以便快速解決kNN查詢與window查詢。此外，我們也實作所設計的索引結構與查詢演算法，並利用 實際空間資料進行實驗。實驗結果顯示我們的方法可以有效處理kNN查詢與window查詢。更重要的是， 從實驗結果可以看出我們的方法的效能受資料量增加的影響相當小，因此我們的方法可說相當具有擴展性。

In recent years, as the popularity of mobile devices with location-aware ability and wide deployment of wireless networks, location-based services have become popular. One of location-based services called spatial query lets user search his/her interested objects which are located nearly from his/her location. Because of the practicability and convenience, spatial query is a popular research topic. As the rapid growth of spatial data, to find an efficient way to store and index the enormous data is an important problem. In this thesis, we use HBase, a distributed database system, to store the enormous spatial data. We also design the corresponding index structures and query algorithms for k nearest neighbor query and window query, the most common query methods. Besides, we implement the index structures and algorithms we designed and use the real spatial data to experiment. The results show that our method could handle k nearest neighbor query and window query effectively. Furthermore, the experiments prove that the increase of spatial data size affects the performance of our method very modestly. It means that our method is very scalable.