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.

目 錄
第一章	緒論	1
1.1	研究背景	1
1.2	研究動機與目的	1
第二章	相關研究	2
2.1	R-Tree	2
2.2	R-Tree的點查詢	6
2.3	R-Tree的區域查詢	8
2.4	R-Tree的應用	10
2.5	基因演算法	10
2.5.1 何謂基因演算法	10
2.5.2 基因演算法的基本架構	11
2.5.3 基因演算法主要運算過程	12
2.6	STR Algorithm	14
2.7	OMT Bulk Loading Algorithm	15
第三章	以基因演算法建置R-Tree	17
3.1	初始族群( Initial Population )	17
3.2	適應函式( Fitness Function )	22
3.3	選擇函式( Selection Function )	22
3.4	交配方式( Crossover )	23
3.5	突變方式( Mutation )	24
3.6	建置R-Tree	25
3.7	根據STR Algorithm結果之基因演算法	27
第四章	實驗與分析	28
4.1	測試資料	29
4.2	實驗結果	34
4.3	實驗結果數據	45
4.4	實驗分析	50
第五章	結論	54
參考文獻	55
 
圖 目 錄
圖 1. 最小邊界矩形	2
圖 2. 節點間的重疊區域	4
圖 3. R-Tree範例	6
圖 4. 點查詢範例	7
圖 5. 點查詢路徑	8
圖 6. 區域查詢範例	9
圖 7. 區域查詢路徑	10
圖 8. 初始族群	18
圖 9. Solution的解譯	19
圖 10. 適當的分群	20
圖 11. 不適當的分群	20
圖 12. matching section	23
圖 13. 突變範例1	25
圖 14. 突變範例2	25
圖 15. 建置R-Tree的流程圖	26
圖 16. 測試資料一( Long Island地區 )	30
圖 17. 測試資料二( Chicago地區 )	30
圖 18. 測試資料三( Detroit地區 )	31
圖 19. 測試資料四( Sacramento地區 )	31
圖 20. 測試資料五( Charlotte地區 )	32
圖 21. 測試資料六( Brooklyn地區 )	32
圖 22. 測試資料七( 虛擬資料 )	33
圖 23. 測試資料一( GA )實驗結果	34
圖 24. 測試資料一( STR )實驗結果	35
圖 25. 測試資料一( GAonSTR )實驗結果	35
圖 26. 測試資料二( GA )實驗結果	36
圖 27. 測試資料二( STR )實驗結果	36
圖 28. 測試資料二( GAonSTR )實驗結果	37
圖 29. 測試資料三( GA )實驗結果	37
圖 30. 測試資料三( STR )實驗結果	38
圖 31. 測試資料三( GAonSTR )實驗結果	38
圖 32. 測試資料四( GA )實驗結果	39
圖 33. 測試資料四( STR )實驗結果	39
圖 34. 測試資料四( GAonSTR )實驗結果	40
圖 35. 測試資料五( GA )實驗結果	40
圖 36. 測試資料五( STR )實驗結果	41
圖 37. 測試資料五( GAonSTR )實驗結果	41
圖 38. 測試資料六( GA )實驗結果	42
圖 39. 測試資料六( STR )實驗結果	42
圖 40. 測試資料六( GAonSTR )實驗結果	43
圖 41. 測試資料七( GA )實驗結果	43
圖 42. 測試資料七( STR )實驗結果	44
圖 43. 測試資料七( GAonSTR )實驗結果	44
圖 44. 群組面積和變化示意圖	51

 
表目錄
表 1. 測試資料一實驗結果數據	45
表 2. 測試資料二實驗結果數據	46
表 3. 測試資料三實驗結果數據	46
表 4. 測試資料四實驗結果數據	47
表 5. 測試資料五實驗結果數據	47
表 6. 測試資料六實驗結果數據	48
表 7. 測試資料七實驗結果數據	48
表 8. 查詢的平均節點拜訪次數	49

[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.
[2]	Bhuyan, J. N., V. V. Raghavan, V. K. Elayavalli, “Genetic algorithm for clustering with an ordered representation”, Belew and Booker, pp. 408-415, 1991.
[3]	Chambers, L., “The Practical Handbook of Genetic Algorithms Applications”, CHAPMAN & HALL / CRC, 2001.
[4]	Falkenauer, E., “Genetic Algorithms and Grouping Problems”, John Wiley & Sons, 1998.
[5]	Gavrila, D. W., “R-Tree Index Optimization”, Tech. Report CS- TR-3292, Univ. of Maryland, College Park, June 1994.
[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.
[9]	Holland, J. H., “Adaptation in Natural and Artificial System”, Ann Arbor: The University of Michigan Press, 1975.
[10]	Jones, D. R., M. A. Beltramo, “Solving partitioning problems with genetic algorithms”, Belew and Booker, pp. 442-449, 1991.
[11]	Koza, J. R., “Survey of Genetic Algorithms and Genetic Programming”, WESCON/'95. Conference, 1995.
[12]	Kumar, A., R. M. Pathak, M. C. Gupta, “Genetic algorithm based approach for designing computer network topology”, Proc. ACM Computer science, 1993.
[13]	Lee, T., S. Lee, “OMT – Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree”, Proceedings of Short Papers at 15th Conference on Advanced Information Systems Engineering (CAiSE’03), Klagenfurt, Austria, 2003.
[14]	Leutengger, S. T., M. Lopez, J. Edgington, “STR: A Simple and Efficient Algorithm for R-Tree Packing”, Proc. of the 14th Int. Conf. on Data Engineering, pp.497-506, 1997.
[15]	Manolopoulos, Y., A. Nanopoulos, A. N. Papadopoulos, Y. Theodoridis, “R-Trees: Theory and Applications”, Springer, 2006.
[16]	Neumann, L., “The R-Tree”, Algorithms and Data Structures for Persistent Data, 2001.
[17]	Popescu, A. R., “A Study of R-tree Based Spatial Access Methods”, University of Helsinki, 2003.
[18]	Reeves, C., “Hybrid genetic algorithms for bin-packing and related problems”, Annals of Operations Research, 1993.
[19]	Rigaux, P., M. Scholl, A. Voisard, “Spatial Databases with application to GIS”, Morgan Kaufmann, 2002.
[20]	Smith, Derek, “Bin packing with adaptive search”, Grefenstette, pp. 202-207, 1985.