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

Geospatial Query Processing on Distributed Database System

白鈞文(Jiun-Wen Bai)

指導教授 ： 陳穎平

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00726

摘要

近年來，隨著行動裝置的普及與無線網路的高覆蓋率，地理位置服務 (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.

並列關鍵字

Spatial Query ； Distributed Database ； Pervasive Computing ； Mobile Computing

參考文獻

[1] I. Junglas and R. Watson, “Location-based services,” Communications of the ACM,

vol. 51, no. 3, 2008.

[2] A. Guttman, “R-trees: a dynamic index structure for spatial searching,” in Proceedings of

[6] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chan-

Implementation, 2006.