利用基因演算法之R-Tree之建置

R-Tree Construction Using Genetic Algorithms

陳柏欽(Po-Chin Chen)

指導教授 ： 梁恩輝

淡江大學/管理學院/資訊管理學系碩士班/碩士(2007年)

https://doi.org/10.6846/TKU.2007.00129

摘要

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 ； 基因演算法 ； STR ； OMT

並列摘要

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.

並列關鍵字

R-Tree ； Genetic Algorithms ； STR ； OMT

參考文獻

[1] Beckman, N., H. P. Kriegel, “The R* tree: An efficient and robust access method for points and rectangles”, Proc. ACM SIGMOD, pp. 322-331, 1990.

[4] Falkenauer, E., “Genetic Algorithms and Grouping Problems”, John Wiley & Sons, 1998.

[6] Goldberg, D. E., “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, 1998.

[7] Guttman, A., “R-Tree : A Dynamic Index Structure for Spatial Searching”, Proc. ACM SIGMOD, pp.47-57, 1984.

[8] Haupt, R. L., “An introduction to genetic algorithms for electromagnetics”, IEEE Antennas, 1995.