R-Tree是一種被廣泛使用在空間及多維度資料庫的多維度資料索引技巧[14]，由Guttman在1984年提出。優良的R-Tree可令查詢動作更有效率，且應具有「目錄矩形涵蓋區域面積較小」及「目錄矩形間重疊的區域面積較小」兩特性[17]。建置R-Tree的主要工作，在於為空間物件依其所在位置取得良好的分組。在過去的研究中，對於建置R-Tree只採用特定的演算法，難以應付真實空間物件在分佈上的多種可能性，以致時常建置出查詢效率不佳的R-Tree。因此，為能普遍因應各種空間資料之特性，本研究利用基因演算法( Genetic Algorithms )「尋求最佳解」的能力，建置R-Tree。本研究透過實驗與Sort-Tile-Recursive( STR ) Algorithm[14]及Overlap Minimizing Top-down( OMT ) Bulk Loading Algorithm[13]進行比較與分析，說明本研究所提出之演算法的成效。 R-tree is a common indexing technique for multi-dimensional data and is widely used in spatial and multi-dimensional databases[14]. It was proposed by Guttman in 1984. A quality R-Tree can make the query more efficient. It should satisfy two properties: “less overlap between the directory rectangles” and “less area of directory rectangles”[17]. The main work to construct an efficient R-Tree is to group the spatial objects well according to their position. In past research, R-Trees are usually implemented using specific algorithms. However, specific algorithms can not deal with various possibilities of distribution for spatial objects. Hence, inefficient R-Trees are usually implemented. In order to construct efficient R-Trees over all kinds of datasets, we make use of Genetic Algorithms which can search for optimal solution to construct R-Trees. Finally, we compared the R-Trees implemented by our methods with those implemented by Sort-Tile-Recursive( STR ) Algorithm[14] and Overlap Minimizing Top-down( OMT ) Bulk Loading Algorithm[13], and then analyzed the fruitage of our methods.
