空間資料庫有效索引改善方式及應用

Abstract

在本論文中我們探討在空間資料庫搜尋大量物件資料所面臨耗時與效率的問題. 因此運用新式的儲存與索引架構透過有效提高索引的方法以及經驗與實驗為根據藉此能夠提升搜尋時的效能. 論文中演算法提供了一種利用R-Tree與雜湊法(Hashing)相結合的精簡方式來導引空間資料的搜尋並且探討如何利用這方法來強化存取大型空間資料庫. R-Tree 運用方形邊界範圍來決定是否要進行搜尋其中的節點. 透過這方式絕大部分樹的節點在搜尋時會過濾,也正因為如此R-Tree適合在資料庫中運用分開索引與資料方式來處理運作. 同時我們也審視和分析現今常用樹狀結構的演算法並且也確實察覺論文中提出的新方式能夠在大型資料庫中利用現有的架構來縮短搜尋時間. 我們採用了大量載入(bulk-loading)與雜湊(Hashing)資料的方式並且在實驗中證明新的觀點能夠在空間資料庫做搜尋時更省時更有效率.

In this thesis we assess the efficiency issue when retrieving sets of objects from a very large spatial database. Thus enhanced performance will be empirically shown here through the new storing and indexing structure. The algorithm provides a condensed method to guide a spatial search and to enhance large data access operations by integrating hashing and R-Tree together. R-tree uses the bounding boxes to decide whether or not to search inside of a child node. In this way most of the nodes in the tree are proved during a search which makes R-trees become more suitable for database operations. We analyze current tree-based algorithms and verify that the new approach in the thesis improves the efficiency in the current architecture. To accomplish this, we use the bulk loading data with hashing into database together with experiments showing that the new algorithm supports spatial queries on spatial database efficiently.