使用動態索引於分散式資料庫之空間查詢

Abstract

由於行動裝置的普及，所能記錄的訊息顯著增加，特別是多維的地理資訊需要快速處理資訊，以便進行資料查詢擷取，以往在關聯式資料庫開發應用程式，然而關聯式資料庫會隨著資料量增加導致查詢性能下降，故出現NoSQL的基礎架構，具有高可用性與高擴展性，能使應用程序收集與分析海量資料，但NoSQL並不支援多維的空間索引。 在本文中，我們專注於地理空間應用程式，在Apache HBase上建立一套可平行查詢地理資訊的系統。基於多層索引結構，結合網格與四元樹作為一級與二級索引。並透過HBase部份鍵功能，空間資料點輸入後，可動態調整網格索引的網格比例與線性四元樹的深度值，不需要因為空間資料點的疏密重建索引，提供靈活的即時查詢。我們合成均勻與合成傾斜的資料與實際的空間資料，比較查詢效能與其他兩個索引模型:四元樹索引與網格索引。我們的研究結果顯示，多層索引架構有很好的進行擴展，並支持高效能的範圍查詢。

Due to a significant increase in the popularity of mobile devices, the messages, and the data record, especially multi-dimensional geographic information increase dramatically. There is need to quickly process information in order to carry out query fast. In relational database applications, the query performance degrades due to the increase the amount of data. Then NoSQL-based infrastructure appears, it offers high availability, and scalability, enabling applications to collect and analyze massive amounts of data. However, NoSQL does not support multi-dimensional spatial index. In this thesis, we focus on geospatial applications built on Apache HBase system, which supports parallel query processing on geographic information. Based on multi-index structure, we combined the grid and quadtree index to range query, and through partial row key scans of Apache HBase. According to sparse or skewed distribution of spatial data, the system can dynamically adjust the destiny parameter of grid index and depth parameter of linear quadtree. There is not need to rebuild the index. The experimental results demonstrate that the system can provide efficient performance for range query processing.